Make this Ruby array pivot more efficient? A puzzle I was given:


  Description:
  
  Write a method that returns the "pivot" index of a list of integers.
  We define the pivot index as the index where the sum of the numbers on
  the left is equal to the sum of the numbers on the right. Given [1, 4,
  6, 3, 2], the method should return 2, since the sum of the numbers to
  the left of index 2 is equal to the sum of numbers to the right of
  index 2 (1 + 4 = 3 + 2). If no such index exists, it should return -1.
  If there are multiple pivots, you can return the left-most pivot.
  You can write the method in any language.
  
  Make sure that the method:
  
  
  runs successfully
  handles all edge cases
  is as efficient as you can make it!
  


Apparently my solution is not efficient enough:

def pivot(arr)
  results = []
  arr.each_with_index do |n,index|
    last      = arr.size - 1
    sum_left  = arr[0..index].inject(:+)
    sum_right = arr[index..last].inject(:+)
    results &lt;&lt; index if sum_left == sum_right
  end
  results.any? ? results.first : -1
end
Ruby allows -1 as an index that means last, so you don't have to calculate it at all.

Calculating the whole left_sum every time is repeating work since it is always the previous left_sum + arr[index-1] (except for when index = 0). Similarly the right_sum is always the previous right_sum - arr[index].

You don't have to gather all results, so you can terminate early on finding the leftmost solution, or as soon as sum_left > sum_right (assuming there are no negative numbers in arr?) you know there is no solution, so can return -1.

For example (untested)

def find_pivot(arr)
  sum_left = -arr[-1]
  sum_right = arr.inject(:+)
  arr.each_index do |i|
    sum_left  += arr[i-1]
    sum_right -= arr[i]
    if sum_left == sum_right
      return i
    elsif sum_right &lt; sum_left
      # assuming there are no negative numbers we already know there's no solution
      return -1
    end
  end
  return -1 # in case we somehow reach the end without a solution or early termination
end


Initialising sum_left to -arr[-1] is a trick to save on having to add an if statement to detect and handle the first iteration of the loop differently, since it cancels out the effect of sum_left += arr[0-1] which would make sum_left jump to the value of the last value in the array.