CodeWars kata 'Sum Of Pairs'

Question

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 < numbers.length
    y = 0
    while y < numbers.length
      sum_test = numbers[x] + numbers[y]
      if sum_test == sum && x != y && x < 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

Answer 1

You have two nested while loops, so your solution is O(n²). 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

Answer 2

Style Comments:

Whenever you find yourself wanting to do a loop by initializing a variable with a while:

y=0
while y < foo.length
  ...
  y=y+1
end

for more idiomatic Ruby, you generally replace it with the following:

foo.each do |y|
  ...
end

If you need the index, add .with_index:

foo.each.with_index do |y,i|
  ...
end

One thing I recommend for new Rubyists is to try to memorize the methods on Array and Enumerable. That's one of the biggest bangs for the buck if you want to exploit Ruby power.

Performance Comments

As @200_success pointed out, you have two nested loops. Each of which is scanning the entire array, which is essentially a brute force method because you're going to check every combination. In fact, because you didn't start the inner loop at the outer loop's index, you're checking each pair twice (the second time in reverse).

There are several techniques you can employ to speed things up:

• Keep track of the index of the second item in the pair. You can stop iterating when you get there because there will be no smaller indexes, and the smallest index of the pair "wins."
• When looking for the second item in the pair, you can whittle down the number of elements you need to check. Start right after the first item, and there's no need to look further than the last index of the pair.
• Utilize methods such as Array#index to find the index of a particular value. Ruby built-ins are generally your fastest option.

Refactoring

This is more of a from scratch implementation. Let's start by initializing our tracking variables for the last index of the pair's value and the overall "winning" pair (because you can't necessarily stop looking the first time you find a pair).

def sum_pairs(numbers, sum) 
  last_index = numbers.length - 1 
  winning_pair = nil

Now we iterate over all the numbers array, with the index. Also, let's include the optimization where we immediately stop when we get to the last index.

  numbers.each.with_index do |n,i|
    break if i >= last_index

Now let's find the matching pairs. Rather than iterate again, we'll use the Ruby builtin index which will either return an index if there is a match, or nil. Another optimization is to minimize the size of the array we need to find the pair in, by starting after the index of the first pair, and not going any further than the last pair's index (this provides a small improvement, according to the benchmarks below).

    offset = i + 1
    pair = numbers[offset..last_index].index(sum-n)
    next if pair.nil? #no match, move on
    pair += offset #index is relative to the offset, so add it back in

So at this point we've found a match. Check to see if it is a new "winner" by comparing the last pair's index:

    if pair <= last_index
      winning_pair = [n,numbers[pair]]
      last_index = pair
    end

And finally return the winning pair's value. The lack of an explicit return may look weird to you, but it is a common Ruby convention. Ruby returns the value of the last executed statement.

  end

  winning_pair
end

Let's add in the given tests:

#tests
puts [3,7] == sum_pairs([11, 3, 7, 5],       10)
puts [4,2] == sum_pairs([4, 3, 2, 3, 4],      6)
puts nil   == sum_pairs([0, 0, -2, 3],        2)
puts [3,7] == sum_pairs([10, 5, 2, 3, 7, 5], 10)

And when we run it:

true
true
true
true

it works!

Benchmarks

I've benchmarked the original with my two variations and also the answer from @200_success:

pairs = [10, 5, 2, 3, 7, 5, 10, 5, 2, 3, 7, 5, 10, 5, 2, 3, 7, 5, 10, 5, 2, 3, 7, 5, 
         11, 7, 4, 1000, 4, 99, 55, 46, 23, 76, 75, 49, 60, 41, 92, 16, 20, 21, 0, -1]
sum = 21

require 'benchmark'
n = 500000
Benchmark.bm(11) do |x|
  x.report("SrdjaNo1:") {n.times do; sum_pairs(pairs, sum); end}
  x.report("Mark-1:") {n.times do; sum_pairs_mark1(pairs, sum); end}
  x.report("Mark-2:") {n.times do; sum_pairs_mark2(pairs, sum); end}
  x.report("200_success:") {require 'set';n.times do; sum_pairs_200_success(pairs, sum); end}
end

The results:

$ sum_pairs.rb
                  user     system      total        real
SrdjaNo1:   110.953000   0.016000 110.969000 (110.966885)
Mark-1:       7.281000   0.000000   7.281000 (  7.280735)
Mark-2:       7.766000   0.000000   7.766000 (  7.764450)
200_success:  4.156000   0.000000   4.156000 (  4.151558)

Answer 3

I'm not a ruby person, so my answer will be more general. 200_success's answer is way more idiomatic and should perform significantly better due to Set.include' prbably optimized implementation.

I'll also try to make my answer very followable by a beginner

square vs. triangle

First of all let's acknowledge that you don't need to iterate over ALL xand ALL y. because then you'll test x+y and y+x. plus, you have to make a special case for not testing x+x or y+y. think of it this way, suppose we have only 4 numbers. The search space is 4² : 16 potential pairs, but most of them are redundant or even erroneous. Your algorithm performs 16 tests, when 6 are necessary at most. Imagine the search space as a square grid :

000u # 0 :a needed test
00u. # . :a test that's already been made in the other half of the square
0u.. # u : a useless test that may give false positives
u...

we're going to do almost that, but revert the triangle because we need to search the beginning of the table, like this:

0
00
000

all of the hashing you do is useless (and maybe expensive)

when trying to optimize for speed, you need to tune your algorithm so that the first match is the one, instead of finding all matches and trying to recoup after the fact. We'll see how

ruby (with my limited knowledge, may be buggy)

this is very much like success_200's version, but I removed the Set (it is certainly faster but may be confusing to beginners)

def sum_pairs(numbers, sum)
  numbers[1..numbers.length-1].each.with_index do |x,i|
    # notice we iterate from the second item
    # (the first would be compared zero times)
    # beware of a possible confusion : here i is not x's
    # index in numbers, but in numbers[1...],
    # so for the second number, i is 0
    num = sum - x # let's only compute this once :)
    numbers[0..i].each |y| #we look _back_ to be sure to find the first pair
      return [y, x] if y == num #instead of x + y == sum
    end
  end
  return nil #nothing to find
end