Balance Point Index
EasyArrays & Hashing
Problem
Weights are placed in a row on a long plank. You want to put the fulcrum under one of the weights so that the total weight strictly to its left equals the total weight strictly to its right. The weight on the fulcrum itself counts for neither side, and weights may be negative (think of helium balloons).
Given nums, return the smallest index i such that sum(nums[0..i-1]) == sum(nums[i+1..n-1]), or -1 if there is none. An empty side sums to 0.
Example 1
- Input:
- nums = [4, 1, 3, 2, 3]
- Output:
- 2
Left of index 2: 4 + 1 = 5. Right of index 2: 2 + 3 = 5.
Example 2
- Input:
- nums = [1, 2, 3]
- Output:
- -1
The (left, right) sums are (0, 5), (1, 3) and (3, 0); none are equal.
Example 3
- Input:
- nums = [3, -3, 5]
- Output:
- 2
Left of index 2: 3 - 3 = 0; the right side is empty, so also 0.
Constraints
- 1 ≤ nums.length ≤ 10^5
- -1000 ≤ nums[i] ≤ 1000
Hint
Show the first hint
If you knew the total of the whole array and the sum to the left of i, could you get the sum to the right of i?
Walkthrough
How to approach it
01Clarify before coding
- Does nums[i] belong to either side? No, it is excluded from both.
- What if several indices work? Return the smallest.
- Is the sum of an empty side 0? Yes, so index 0 or n - 1 can be answers.
02Brute force
For each index, sum the elements to its left and to its right from scratch and compare.
Cost: O(n²) time: each index costs a full scan, 10^10 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.