Left and Right Sum Differences

EASY

Description

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] <= 10⁵

Approaches

Checkout 4 different approaches to solve Left and Right Sum Differences. Click on different approaches to view the approach and algorithm in detail.

Optimal Two-Pass In-place Calculation

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 answer array of size n.
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.
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].
Return answer.

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 Analysis

Time Complexity: O(n), as it involves two separate, non-nested passes over the array.Space Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Left and Right Sum Differences. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Left and Right Sum Differences

Patterns:

Prefix Sum

Data Structures:

Array