Left and Right Sum Differences
EasyPrompt
You are given a 0-indexed integer array nums of size n.
Define two arrays leftSum and rightSum where:
leftSum[i]is the sum of elements to the left of the indexiin the arraynums. If there is no such element,leftSum[i] = 0.rightSum[i]is the sum of elements to the right of the indexiin the arraynums. If there is no such element,rightSum[i] = 0.
Return an integer array answer of size n where answer[i] = |leftSum[i] - rightSum[i]|.
Example 1:
Input: nums = [10,4,8,3]
Output: [15,1,11,22]
Explanation: The array leftSum is [0,10,14,22] and the array rightSum is [15,11,3,0].
The array answer is [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22].Example 2:
Input: nums = [1]
Output: [0]
Explanation: The array leftSum is [0] and the array rightSum is [0].
The array answer is [|0 - 0|] = [0].
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 105
Approaches
4 approaches with complexity analysis and trade-offs.
This approach is one of the most efficient in terms of both time and space. It cleverly uses the output array itself to store intermediate values (the left sums), thus avoiding the need for any extra arrays or a pre-computation of the total sum. It computes the final result in two separate passes.
Algorithm
- Initialize an
answerarray of sizen. - First Pass (Left-to-Right):
- Initialize
prefixSum = 0. - Iterate from
i = 0ton-1. - Set
answer[i] = prefixSum. - Update
prefixSum += nums[i]. - After this pass,
answercontains allleftSumvalues.
- Initialize
- Second Pass (Right-to-Left):
- Initialize
suffixSum = 0. - Iterate from
i = n-1down to0. - Update
answer[i]with the final value:answer[i] = Math.abs(answer[i] - suffixSum). - Update
suffixSum += nums[i].
- Initialize
- Return
answer.
Walkthrough
This is another optimal O(n) time and O(1) extra space solution. It works by first populating the result array with one set of values (the left sums) and then updating it with the other (the right sums).
In the first pass, from left to right, we calculate the prefix sum. For each index i, we store the sum of elements to its left directly into answer[i].
In the second pass, from right to left, we calculate the suffix sum. For each index i, answer[i] already holds leftSum[i]. We can now calculate the final result by taking the absolute difference between this value and the current suffixSum (which represents rightSum[i]).
class Solution { public int[] leftRightDifference(int[] nums) { int n = nums.length; int[] answer = new int[n]; // First pass: Calculate leftSum and store in answer array int prefixSum = 0; for (int i = 0; i < n; i++) { answer[i] = prefixSum; prefixSum += nums[i]; } // Second pass: Calculate rightSum and find the absolute difference int suffixSum = 0; for (int i = n - 1; i >= 0; i--) { answer[i] = Math.abs(answer[i] - suffixSum); suffixSum += nums[i]; } return answer; }}Complexity
Time
O(n), as it involves two separate, non-nested passes over the array.
Space
O(1) extra space. The calculation is done in-place within the result array, so no additional data structures are needed besides the output array itself.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1) extra space.
Elegant solution that reuses the output array for intermediate calculations.
Cons
The logic might be slightly less direct to grasp on first look compared to the total sum approach, as it modifies the answer array in place.
This is the most straightforward and intuitive approach. For each element in the input array, we simply iterate through all elements to its left to compute leftSum and all elements to its right to compute rightSum. We then find the absolute difference and store it.
Algorithm
- Initialize an
answerarray of sizen. - Iterate through the input array
numswith an indexifrom0ton-1. - For each
i, initializeleftSum = 0andrightSum = 0. - Start a nested loop to calculate
leftSum: iterate fromj = 0toi-1and accumulatenums[j]. - Start another nested loop to calculate
rightSum: iterate fromj = i+1ton-1and accumulatenums[j]. - Calculate
answer[i] = Math.abs(leftSum - rightSum). - After the outer loop completes, return the
answerarray.
Walkthrough
The brute-force method directly translates the problem definition into code. We use a main loop to go through each index i of the nums array. Inside this loop, we use two separate inner loops: one to sum up all elements with indices less than i (leftSum), and another to sum up all elements with indices greater than i (rightSum). While this approach is easy to understand, its performance degrades quickly as the size of the input array increases because for each of the n elements, we are potentially iterating over n other elements.
class Solution { public int[] leftRightDifference(int[] nums) { int n = nums.length; int[] answer = new int[n]; for (int i = 0; i < n; i++) { int leftSum = 0; // Calculate leftSum for (int j = 0; j < i; j++) { leftSum += nums[j]; } int rightSum = 0; // Calculate rightSum for (int j = i + 1; j < n; j++) { rightSum += nums[j]; } answer[i] = Math.abs(leftSum - rightSum); } return answer; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. For each element, we traverse parts of the array, leading to nested loops.
Space
O(n) to store the output array `answer`. If the output array is not considered extra space, the complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space other than the output array.
Cons
Highly inefficient for larger arrays due to the quadratic time complexity.
Performs many redundant calculations, as sums are recomputed for each element.
This approach improves upon the brute-force method by pre-calculating all the left sums and right sums to avoid redundant computations. We use two auxiliary arrays, one for prefix sums (leftSum) and one for suffix sums (rightSum), and then combine them to get the final result.
Algorithm
- Create three arrays of size
n:leftSum,rightSum, andanswer. - Calculate
leftSumarray:- Initialize
leftSum[0] = 0. - Loop from
i = 1ton-1, settingleftSum[i] = leftSum[i-1] + nums[i-1].
- Initialize
- Calculate
rightSumarray:- Initialize
rightSum[n-1] = 0. - Loop from
i = n-2down to0, settingrightSum[i] = rightSum[i+1] + nums[i+1].
- Initialize
- Calculate
answerarray:- Loop from
i = 0ton-1, settinganswer[i] = Math.abs(leftSum[i] - rightSum[i]).
- Loop from
- Return
answer.
Walkthrough
To optimize the sum calculations, we can compute all leftSum values in one pass and all rightSum values in another.
First, we create a leftSum array. leftSum[i] will store the sum of all elements before index i. We can compute this in a single pass from left to right.
Next, we create a rightSum array. rightSum[i] will store the sum of all elements after index i. This is computed in a single pass from right to left.
Finally, with both leftSum and rightSum arrays fully populated, we can iterate through them one last time and calculate answer[i] = |leftSum[i] - rightSum[i]| for each index.
class Solution { public int[] leftRightDifference(int[] nums) { int n = nums.length; int[] leftSum = new int[n]; int[] rightSum = new int[n]; int[] answer = new int[n]; // Calculate leftSum array // leftSum[0] is implicitly 0 for (int i = 1; i < n; i++) { leftSum[i] = leftSum[i - 1] + nums[i - 1]; } // Calculate rightSum array // rightSum[n-1] is implicitly 0 for (int i = n - 2; i >= 0; i--) { rightSum[i] = rightSum[i + 1] + nums[i + 1]; } // Calculate the final answer array for (int i = 0; i < n; i++) { answer[i] = Math.abs(leftSum[i] - rightSum[i]); } return answer; }}Complexity
Time
O(n). We make three separate passes through the array (one for left sums, one for right sums, one for the final answer), each taking O(n) time. The total complexity is O(n) + O(n) + O(n) = O(n).
Space
O(n). We use two additional arrays, `leftSum` and `rightSum`, each of size `n`, in addition to the `answer` array.
Trade-offs
Pros
Significantly more efficient than the brute-force approach, with a linear time complexity.
The logic is still quite clear and follows the problem definition closely.
Cons
Requires O(n) extra space for the two auxiliary arrays, which can be significant for very large inputs.
This is a space-optimized approach that achieves linear time complexity with constant extra space. Instead of storing the entire rightSum array, we calculate it on the fly. The key insight is that for any index i, the sum of elements to its right is equal to the total sum of the array minus the sum of elements to its left and the element at i itself (rightSum[i] = totalSum - leftSum[i] - nums[i]).
Algorithm
- First pass: Iterate through
numsto calculate thetotalSumof all elements. - Initialize a variable
leftSum = 0. - Create the
answerarray of sizen. - Second pass: Iterate through
numswith indexifrom0ton-1.- Calculate the current
rightSumusing the formula:rightSum = totalSum - leftSum - nums[i]. - Compute
answer[i] = Math.abs(leftSum - rightSum). - Update
leftSumfor the next iteration:leftSum += nums[i].
- Calculate the current
- Return the
answerarray.
Walkthrough
This method avoids the O(n) extra space of the previous approach. It works in two passes. The first pass is a simple loop to compute the sum of all elements in the array, let's call it totalSum. The second pass iterates through the array again to build the answer. In this pass, we maintain a running leftSum. For each index i, we can derive the rightSum without another loop. After calculating answer[i], we update leftSum by adding nums[i] to prepare it for the next index.
class Solution { public int[] leftRightDifference(int[] nums) { int n = nums.length; int[] answer = new int[n]; int totalSum = 0; for (int num : nums) { totalSum += num; } int leftSum = 0; for (int i = 0; i < n; i++) { int rightSum = totalSum - leftSum - nums[i]; answer[i] = Math.abs(leftSum - rightSum); leftSum += nums[i]; } return answer; }}Complexity
Time
O(n). We make two passes over the array: one to compute the total sum and another to compute the answer. This is O(n) + O(n) = O(n).
Space
O(1) extra space. We only use a few variables to store `totalSum` and `leftSum`. The O(n) space for the output array is not counted as extra space.
Trade-offs
Pros
Optimal time complexity of O(n).
Space-efficient, using O(1) extra space (not counting the output array).
Cons
Requires two full passes over the input array.
Solutions
Solution
class Solution {public int[] leftRigthDifference(int[] nums) { int left = 0, right = Arrays.stream(nums).sum(); int n = nums.length; int[] ans = new int[n]; for (int i = 0; i < n; ++i) { right -= nums[i]; ans[i] = Math.abs(left - right); left += nums[i]; } return ans; }}class Solution {public: vector<int> leftRigthDifference(vector<int> &nums) { int left = 0, right = accumulate(nums.begin(), nums.end(), 0); vector<int> ans; for (int &x : nums) { right -= x; ans.push_back(abs(left - right)); left += x; } return ans; }};class Solution: def leftRigthDifference(self, nums: List[int]) -> List[int]: left, right = 0, sum(nums) ans = [] for x in nums: right -= x ans . append(abs(left - right)) left += x return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.