#2574
Left and Right Sum Differences
Easy Prefix & suffix
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
For every index, return the absolute difference between the sum of elements to its left and the sum of elements to its right.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: for each index, |sum on the left - sum on the right|.
Why this works: same trick as the pivot index: right = total - left - nums[i].
Example: [10, 4, 8, 3], total 25
i=0: left 0, right 15 → 15i=1: left 10, right 11 → 1i=2: left 14, right 3 → 11i=3: left 22, right 0 → 22
✦Hints open one at a time
Same idea as pivot index: right = total - left - nums[i].
You don't need separate prefix and suffix arrays.
↗Approach
Compute the total, then sweep once keeping the left sum and filling |left - right| for each index.
</>Solution (Java)
class Solution {
public int[] leftRightDifference(int[] nums) {
int total = 0;
for (int x : nums) total += x;
int[] ans = new int[nums.length];
int left = 0;
for (int i = 0; i < nums.length; i++) {
int right = total - left - nums[i];
ans[i] = Math.abs(left - right);
left += nums[i];
}
return ans;
}
}!Common mistake
Including nums[i] in either side.
Complexity
- Time: O(n).
- Space: O(1) extra besides the output.
