It runs locally but the site gives me a 'Time Limit Exceeded' error


  • 1
    M

    My code is below. Any input will be highly appreciated!

    def two_sum(numbers, target)
      output = []
    
      numbers.each_with_index do |element, index|
        difference = target - element
    
        numbers.each_with_index do |el2, i2|
          next if i2 == index
          output << i2 if el2 == difference
        end
      end
    
      return output.sort.map { |index| index + 1}
    end

  • 2
    S

    Hi there, I initially did the same way but then I tried this and it worked:

    def two_sum(numbers, target)
      numbers.each_with_index do |number, index|
        difference  = target - number
        if numbers.include?(difference) && index != numbers.index(difference)
          index2 = numbers.index(difference)
          return [index + 1, index2 + 1].sort
        end
      end
    end
    

    The "exceeded time limit" error is because the code is taking too long when the array is very large. I believe your code has a time complexity of (n^2), which isn't ideal. The above code has a time complexity of (n). ; )


  • 0
    M

    Oh damn! Gracias, Saleh :D


  • 0
    T

    I doubt your code has a time complexity of (n^2) too!
    numbers.index(difference) is equal to find an number in an array which has a time complexity of (n)!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.