728. The Balance Point
Find the smallest index i such that everything strictly to the LEFT of i adds up to the
same total as everything strictly to the RIGHT of it. Print that index, using 0-based numbering,
or -1 if there is none.
The value AT position i belongs to neither side. Values may be negative.
1 7 3 6 5 6 -> 3 left 1+7+3 = 11, right 5+6 = 11
2 1 -1 -> 0 left is empty, right 1 + (-1) = 0
1 2 3 -> -1
## The empty side is a real side
At index 0 the left side is empty and totals 0. At index n-1 the right side is empty and
totals 0. Both are legal answers, and an implementation that starts its scan at index 1 or stops
at n-2 misses them.
2 1 -1 answers 0 for exactly that reason, and 0 on its own answers 0 because both sides are
empty.
## One total, one running left
There is no need to sum the right side at each step. Take the whole total once, then carry the left total as the scan advances:
right side at i = total - left - a[i]
so the test is
left == total - left - a[i]
and left grows by a[i] afterwards. One pass, one extra variable.
Recomputing the right side inside the loop is O(n^2) and gives the same answers, so this is
purely about the second pass being unnecessary.
## The order inside the loop
Test BEFORE adding a[i] to the left total. Adding first puts a[i] on the left, where it
does not belong, and shifts every answer by one.
## Negative values
The totals can be negative and the sides can both be negative. Nothing in the method cares, which is worth stating because several prefix-sum problems in this block DO require positive values and say so.
## Overflow
200000 values of magnitude 10^9 total 2 * 10^14.
## What most people try first
Summing the right side again at every index. That is correct and it is O(n^2), which is
4 * 10^10 operations at the limit. The whole problem is noticing that the right side is the
total minus the left, so the second pass is unnecessary.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers, which may be negative.
Output
Print one integer, the smallest balance index, or -1.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.