Left side, right side
Use the total and a running sum to compare both sides of every position. About 8 minutes.
A see-saw with a pivot
Picture weights in a row on a plank. Is there a spot to put the pivot so the weight on the left equals the weight on the right? The weight right on the pivot counts for neither side.
You could add up both sides for every spot, but that repeats a lot of work. Here's the shortcut: add up everything once. Then for any spot, if you know the left side, the right side is simply what's left over.
left 0, right 28 − 0 − 1 = 27. Not equal.
Carry the left side as you walk
Start with the left side at 0. At each spot, work out the right side, compare the two, and only then add this spot's weight to the left side before moving on.
The order matters: the weight on the pivot belongs to neither side, so it joins the left side only after you've compared.
total = sum(nums)
left = 0
for i, x in enumerate(nums):
right = total - left - x
if left == right:
return i
left += x
return -1Everything adds up to 10. The left side is 3, and the weight on the pivot is 4. What's the right side?
- A3
- B7
- C6
Show the answer
3. 10 − 3 − 4 = 3. It balances!
Balance point
You get a list of numbers. Find the first position i where the sum of the numbers before i equals the sum of the numbers after i (nums[i] itself is on neither side). An empty side sums to 0. Return i, or −1 if there's no such position.
nums = [1, 7, 3, 6, 5, 6] → 3
0 ≤ n ≤ 1,000,000 · −10^6 ≤ each value ≤ 10^6 · sums can pass 2^31: use longs