Scale Engineer

Left and Right Sum Differences

Easy
#2354Time: 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.
Patterns
Prefix Sum
Data structures
Array

Prompt

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 index i in the array nums. If there is no such element, leftSum[i] = 0.
  • rightSum[i] is the sum of elements to the right of the index i in the array nums. 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 <= 1000
  • 1 <= 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

  1. Initialize an answer array of size n.
  2. First Pass (Left-to-Right):
    • Initialize prefixSum = 0.
    • Iterate from i = 0 to n-1.
    • Set answer[i] = prefixSum.
    • Update prefixSum += nums[i].
    • After this pass, answer contains all leftSum values.
  3. Second Pass (Right-to-Left):
    • Initialize suffixSum = 0.
    • Iterate from i = n-1 down to 0.
    • Update answer[i] with the final value: answer[i] = Math.abs(answer[i] - suffixSum).
    • Update suffixSum += nums[i].
  4. 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.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem