# Left and Right Sum Differences
**Difficulty:** EASY
[External](https://leetcode.com/problems/left-and-right-sum-differences)
Canonical: https://scaleengineer.com/dsa/problems/left-and-right-sum-differences
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
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
## Brute Force with Nested Loops
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Initialize an `answer` array of size `n`.
2. Iterate through the input array `nums` with an index `i` from `0` to `n-1`.
3. For each `i`, initialize `leftSum = 0` and `rightSum = 0`.
4. Start a nested loop to calculate `leftSum`: iterate from `j = 0` to `i-1` and accumulate `nums[j]`.
5. Start another nested loop to calculate `rightSum`: iterate from `j = i+1` to `n-1` and accumulate `nums[j]`.
6. Calculate `answer[i] = Math.abs(leftSum - rightSum)`.
7. After the outer loop completes, return the `answer` array.

## Using Prefix and Suffix Sum Arrays
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Create three arrays of size `n`: `leftSum`, `rightSum`, and `answer`.
2. **Calculate `leftSum` array:**
   - Initialize `leftSum[0] = 0`.
   - Loop from `i = 1` to `n-1`, setting `leftSum[i] = leftSum[i-1] + nums[i-1]`.
3. **Calculate `rightSum` array:**
   - Initialize `rightSum[n-1] = 0`.
   - Loop from `i = n-2` down to `0`, setting `rightSum[i] = rightSum[i+1] + nums[i+1]`.
4. **Calculate `answer` array:**
   - Loop from `i = 0` to `n-1`, setting `answer[i] = Math.abs(leftSum[i] - rightSum[i])`.
5. Return `answer`.

## Two-Pass Approach using Total Sum
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]`).
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. First pass: Iterate through `nums` to calculate the `totalSum` of all elements.
2. Initialize a variable `leftSum = 0`.
3. Create the `answer` array of size `n`.
4. Second pass: Iterate through `nums` with index `i` from `0` to `n-1`.
   - Calculate the current `rightSum` using the formula: `rightSum = totalSum - leftSum - nums[i]`.
   - Compute `answer[i] = Math.abs(leftSum - rightSum)`.
   - Update `leftSum` for the next iteration: `leftSum += nums[i]`.
5. Return the `answer` array.

## 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.
**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.
**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.
### Explanation
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]`).

```java
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;
    }
}
```
### 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`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
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 ans

```