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 << 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 < 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.

StackExchange Code Review Q#40226, answer score: 8