Find indices of first pair of numbers that sums to zero

The problem can be solved in less than quadratic time. Sort the elements by absolute value, then search for consecutive elements that sum up to zero.

def two_sum(nums) temp = nums.map.with_index { |x, i| [x, i] } temp.sort_by! { |x| x[0].abs } for x in temp.zip(temp.rotate) if x[0][0] + x[1][0] == 0 return [x[0][1], x[1][1]] end end return nil end 

You can use return also within a loop block to exit the method.

Here is my solution, which populates an Hash, were the keys are the numbers and the values are the indexes. If I found a key, that is the minus value, I finish the loop. Otherwise if the number is a new one, it is added to the Hash.

def zero_sums(ns) ns.each_with_index.with_object({}) do |(n,i),o| return o[-n], i if o.key?(-n) o[n] = i unless o.key?(n) end end 

Naïve approach:

def zero_sums(array) array[0...-1].each_with_index do |n, i| j = array[(i+1)..-1].index(-n) return [i, j + i + 1] if j end end zero_sums([-1, -2, 2, 1]) # => [0, 3] 

It simply loops through the values, and for each value it attempts to find a its "inverse" in the remaining array using #index.

A possibly faster approach could be this:

def zero_sums(array) sorted = array.each_with_index.sort_by(&:first) sorted[0...-1].each do |n, i| other = sorted[(i+1)..-1].bsearch { |m, j| m == -n } return [i, other.last] if other end end zero_sums([-1, -2, 2, 1]) # => [1,2] 

• Make an array of [value, index] tuples
• Sort it by the values
• Again loop through, but use #bsearch to more quickly search the remaining array for the needed value, though if there are many repeats of the desired value, this may not find the lowest index

As seen above, given the same input, [-1, -2, 2, 1], for first method return [0, 3] while the second returns [1, 2]. Both are accurate, but, as vnp mentioned in a comment, it's not totally clear which one is "first"

All answers given here are good, but I would like to show the absolute simplest solution to show the power of Ruby:

x.product(x).detect{|a,b| a + b == 0} 

Now product gives the Cartesian product pairing each number of the first list with each number of the second list,

For example:

irb(main):013:0> [1, 2, 3].product(["a", "b", "c"]) => [[1, "a"], [1, "b"], [1, "c"], [2, "a"], [2, "b"], [2, "c"], [3, "a"], [3, "b"], [3, "c"]] 

In our case for example given x = [1, 4, -1, 5, -4] this returns:

irb(main):011:0> x.product(x) => [[1, 1], [1, 4], [1, -1], [1, 5], [1, -4], [4, 1], [4, 4], [4, -1], [4, 5], [4, -4], [-1, 1], [-1, 4], [-1, -1], [-1, 5], [-1, -4], [5, 1], [5, 4], [5, -1], [5, 5], [5, -4], [-4, 1], [-4, 4], [-4, -1], [-4, 5], [-4, -4]] 

That is if we take the Cartesian product of a list with itself we get all of the pairs.

detect returns the first value that satisfies the given predicate, that in this case is that the sum of the two elements be 0.

So:

irb(main):010:0> x.product(x).detect{|a,b| a + b == 0} => [1, -1]