CodeWars kata 'Sum Of Pairs' I need help in optimizing my code for this challenge. I think my algorithm is fine and I pass all sample tests but get took longer than 12000ms to complete error for final one.

I guess there are a lot of unnecessary variables but this is all my beginners Ruby brain could think of. :)

I have started learning coding 2 weeks ago so style-wise this is most certainly horrible.

Kata link


  Instructions : 
  
  Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.
  Negative numbers and duplicate numbers can and will appear.
  
  NOTE: There will also be lists tested of lengths upwards of 10,000,000 elements. Be sure your code doesn't time out.


def sum_pairs(numbers, sum) 
  # Idea was :
  #  1. To iterate over array elements take their sum and add
  #     it to hash if it is equal to "sum". 
  #  2. Sort hash by value to find lowest second parameter since
  #     we need entire pair to be first not just first element.
  #  3. Convert that hash to array so that I could take value 
  #      of those elements and return actual numbers. 
  #     (Didn't know to do it from hash directly :))
  x = 0
  h = {}
  while x &lt; numbers.length
    y = 0
    while y &lt; numbers.length
      sum_test = numbers[x] + numbers[y]
      if sum_test == sum &amp;&amp; x != y &amp;&amp; x &lt; y
        h[x] = y
      end
      y += 1
    end
    x += 1
  end
  if h.empty?
    return nil
  else
    final_positions = h.sort_by {|key, value| value}.first.to_a
    return numbers[final_positions[0]], numbers[final_positions[1]]
  end
end
You have two nested while loops, so your solution is O(n2). A good solution should be possible in O(n) — that is, one pass through numbers.

Also, the while loops are rather clumsy. Idiomatic Ruby would usually use #each to iterate, or #each_with_index if you need the indexes as well. Here, you don't care about the indexes. If you return as soon as you have encountered a solution, it will necessarily be the leftmost solution.

require 'set'

def sum_pairs(numbers, sum)
  seen = Set.new
  numbers.each do |n|
    return [sum - n, n] if seen.include?(sum - n)
    seen.add(n)
  end
  nil
end