Balance Point Index
Problem
Given a list of whole numbers, which may be negative, find a position where the values strictly to its left add up to the same total as the values strictly to its right. An empty side counts as zero. Return the leftmost such index, or -1 if there is none.
Examples
Input: values = [2, 7, 1, 5, 4]
Output: 2
Why: 2 + 7 = 9 on the left of index 2, and 5 + 4 = 9 on the rightInput: values = [1, 2, 3]
Output: -1
Why: no index splits the list into equal sidesInput: values = [5]
Output: 0
Why: edge case, both sides of the only value are empty and sum to 0Hints
0 / 3
Adding up both sides from scratch at every index repeats the same additions over and over, which makes the whole check quadratic.
Once you know the total of the whole list, the right side at any index follows from the left side and the value at that index.
Sum the list once. Then walk it with a running left total: the right total is the grand total minus the left total minus the current value. Return the first index where they match, and add the current value to the left total before moving on.
Solution
One pass computes the grand total, and a second pass keeps a running sum of everything already passed. At each index the right side is whatever is left of the total after removing the left side and the current value, so each check is O(1) instead of O(n). The first match is returned, which makes it the leftmost. Time is O(n), and extra space is O(1).
def balance_point(values):
total = sum(values)
left = 0
for i, v in enumerate(values):
right = total - left - v # everything after index i
if left == right:
return i
left += v
return -1
print(balance_point([2, 7, 1, 5, 4])) # -> 2
print(balance_point([1, 2, 3])) # -> -1
print(balance_point([5])) # -> 0Stuck on the idea rather than the code? O(1) and O(n) covers it.