How to improve algorithm efficiency for nested loop

Question

Given a list of integers and a single sum value, return the first two values (from the left) that add up to form the sum.

For example, given:

sum_pairs([10, 5, 2, 3, 7, 5], 10)

[5, 5] (at indices [1, 5] of [10, 5, 2, 3, 7, 5]) add up to 10, and [3, 7] (at indices [3, 4]) add up to 10. Among them, the entire pair [3, 7] is earlier, and therefore is the correct answer.

Here is my code:

def sum_pairs(ints, s)
  result = []
  i = 0
  while i < ints.length - 1
    j = i+1
    while j < ints.length
      result << [ints[i],ints[j]] if ints[i] + ints[j] == s
      j += 1
    end
    i += 1
  end
  puts result.to_s
  result.min
end

It works, but is too inefficient, taking 12000 ms to run. The nested loop is the problem of inefficiency. How could I improve the algorithm?

Try with ruby-doc.org/core-2.5.1/Array.html#method-i-combination, find which pairs returns the sum, then look for their index in the original array. — iGian
– iGian, Commented Oct 25, 2018 at 5:09

Amadan · Accepted Answer · 2018-10-25 06:38:09Z

6

Have a Set of numbers you have seen, starting empty
Look at each number in the input list
Calculate which number you would need to add to it to make up the sum
See if that number is in the set
If it is, return it, and the current element
If not, add the current element to the set, and continue the loop
When the loop ends, you are certain there is no such pair; the task does not specify, but returning nil is likely the best option

Should go superfast, as there is only a single loop. It also terminates as soon as it finds the first matching pair, so normally you wouldn't even go through every element before you get your answer.

As a style thing, using while in this way is very unRubyish. In implementing the above, I suggest you use ints.each do |int| ... end rather than while.

EDIT: As Cary Swoveland commented, for a weird reason I thought you needed indices, not the values.

edited Oct 25, 2018 at 6:38

answered Oct 25, 2018 at 5:09

Amadan

200k23 gold badges252 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Cary Swoveland Over a year ago

I don't think the OP needs the indices, just the numbers, Had you read it that way I expect you would have suggested what I have done in my answer.

Amadan Over a year ago

@CarySwoveland: Ah indeed, not sure why I thought indices were wanted :/ Yeah, your code is what I was trying to get OP to try to write :D

Stefan · Accepted Answer · 2018-10-25 07:32:54Z

4

require 'set'

def sum_pairs(arr, target)
  s = Set.new
  arr.each do |v|
    return [target-v, v] if s.include?(target-v)
    s << v
  end
  nil
end

sum_pairs [10, 5, 2, 3, 7, 5], 10
  #=> [3, 7]
sum_pairs [10, 5, 2, 3, 7, 5], 99
  #=> nil

I've used Set methods to speed include? lookups (and, less important, to save only unique values).

edited Oct 25, 2018 at 7:32

Stefan

115k14 gold badges157 silver badges234 bronze badges

answered Oct 25, 2018 at 6:25

Cary Swoveland

111k6 gold badges69 silver badges105 bronze badges

Comments

Dyaniyal Wilson · Accepted Answer · 2018-10-25 06:51:35Z

1

Try below, as it is much more readable.

def sum_pairs(ints, s)
  ints.each_with_index.map do |ele, i|
    if ele < s
      rem_arr = ints.from(i + 1)
      rem = s - ele
      [ele, rem] if rem_arr.include?(rem)
    end
  end.compact.last
end

answered Oct 25, 2018 at 6:51

Dyaniyal Wilson

1,07010 silver badges14 bronze badges

2 Comments

Heiman Chan Over a year ago

Sorry I'm still a beginner, I don't understand what end.compact.last does. My understanding would be with that line, we don't have to define a variable to store the .map result of the rem_arr, right?

Heiman Chan Over a year ago

Also, why is the .from method undefined?

iGian · Accepted Answer · 2018-10-25 20:59:39Z

0

One liner (the fastest?)

ary = [10, 0, 8, 5, 2, 7, 3, 5, 5]
sum = 10

def sum_pairs(ary, sum)
  ary.map.with_index { |e, i|  [e, i] }.combination(2).to_a.keep_if { |a| a.first.first + a.last.first == sum }.map { |e| [e, e.max { |a, b| a.last <=> b.last }.last] }.min { |a, b| a.last <=> b.last }.first.map{ |e| e.first }
end

Yes, it's not really readable, but if you add methods step by step starting from ary.map.with_index { |e, i| [e, i] } it's easy to understand how it works.

edited Oct 25, 2018 at 20:59

answered Oct 25, 2018 at 20:54

iGian

11.2k3 gold badges24 silver badges38 bronze badges

Collectives™ on Stack Overflow

How to improve algorithm efficiency for nested loop

4 Answers 4

2 Comments

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related