Split the Night Market
A night market runs along one street. After closing, each stall reports its net result for the evening: a positive number for a profit, a negative one for a loss.
Two organizers share the street. They pick one stall as the dividing line: everything to its left belongs to one organizer, everything to its right to the other, and the dividing stall itself is the market's own and counts for neither. They want a dividing stall that makes both sides total exactly the same.
Your task
Write fairSplit(results). Return the smallest index i such that the sum of results[0..i-1] equals the sum of results[i+1..end]. A side with no stalls sums to 0.
If no index works, or the list is empty, return -1.
fairSplit(results: int[]) → int
Examples
results = [2, 5, -1, 4, 3, 3]
3
Divide at index 3 (the stall that made 4). Left: 2 + 5 + (-1) = 6. Right: 3 + 3 = 6. No earlier index balances: at index 2, for example, the left is 7 and the right is 10.
results = [4, -4, 9]
2
Divide at the last stall, index 2. Left: 4 + (-4) = 0. Right: no stalls, so 0. The dividing stall can be at either end of the street.
results = [1, 2, 3]
-1
Index 0 gives 0 against 5, index 1 gives 1 against 3, index 2 gives 3 against 0. Nothing balances, so return -1.
Constraints
- 0 ≤ results.length ≤ 100,000
- -10,000 ≤ results[i] ≤ 10,000
Start with brute force
Try every index as the divider and add up both sides from scratch with two loops.
Each try reads the whole list, so the cost is about n² additions. With 100,000 stalls that is 10 billion additions, nearly all of them repeated from the previous try: moving the divider one step only moves one stall from one side to the other.
Hints
0 of 4 shown- Hint 1
In the first example, say you already know the left side at index 3 totals 6. Without adding the right side up stall by stall, how could you work out its total?
- Hint 2
Everything on the street adds up to one fixed total. The right side is that total, minus the left side, minus the dividing stall.
- Hint 3
So you need two numbers: the total of the whole street, computed once, and the total of the stalls to the left of where you stand. How does the left total change when you step one stall to the right?
- Hint 4
Add up the whole list once to get
total. Then walk from the left withleft = 0. At each index, the right side istotal - left - results[i]. If it equalsleft, returni. Otherwise addresults[i]toleftand move on.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
You do not need to add up the right side at all. Once you know the street total and the left side, the right side is whatever is left over after you take out the dividing stall.
Trace [2, 5, -1, 4, 3, 3]. The total is 16.
- Index 0: left 0, right 16 - 0 - 2 = 14. Not equal. left becomes 2.
- Index 1: left 2, right 16 - 2 - 5 = 9. left becomes 7.
- Index 2: left 7, right 16 - 7 - (-1) = 10. left becomes 6.
- Index 3: left 6, right 16 - 6 - 4 = 6. Equal, return 3.
Notice that left went down at index 2. With negative numbers the running sum is not always growing, which is why a "move two pointers in from both ends" idea does not work here. Also check before adding the current stall to left: the divider belongs to neither side.
function fairSplit(results) {
let total = 0;
for (const r of results) total += r;
let left = 0; // sum of stalls before index i
for (let i = 0; i < results.length; i++) {
const right = total - left - results[i];
if (left === right) return i;
left += results[i]; // stall i moves to the left side
}
return -1;
}def fair_split(results):
total = sum(results)
left = 0 # sum of stalls before index i
for i, r in enumerate(results):
right = total - left - r
if left == right:
return i
left += r # stall i moves to the left side
return -1Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.