Problem

Given a 0-indexed integer array nums, find a 0-indexed integer array answer where:

  • answer.length == nums.length.
  • answer[i] = |leftSum[i] - rightSum[i]|.

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 the array answer.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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^5

Solution

Method 1 – Prefix Sums

Intuition

To efficiently compute the left and right sums for each index, we can use prefix sums. By precomputing the total sum and iterating through the array, we can update left and right sums in a single pass.

Approach

  1. Compute the total sum of the array.
  2. Initialize left_sum as 0.
  3. For each index i, the right sum is total_sum - left_sum - nums[i].
  4. Compute |left_sum - right_sum| for each index and update left_sum by adding nums[i].
  5. Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<int> leftRightDifference(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        int total = 0, left = 0;
        for (int x : nums) total += x;
        for (int i = 0; i < n; ++i) {
            int right = total - left - nums[i];
            ans[i] = abs(left - right);
            left += nums[i];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func leftRightDifference(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    total, left := 0, 0
    for _, x := range nums { total += x }
    for i, x := range nums {
        right := total - left - x
        ans[i] = abs(left - right)
        left += x
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x } else { return x } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int[] leftRightDifference(int[] nums) {
        int n = nums.length, total = 0, left = 0;
        int[] ans = new int[n];
        for (int x : nums) total += x;
        for (int i = 0; i < n; i++) {
            int right = total - left - nums[i];
            ans[i] = Math.abs(left - right);
            left += nums[i];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun leftRightDifference(nums: IntArray): IntArray {
        val n = nums.size
        val ans = IntArray(n)
        var total = nums.sum()
        var left = 0
        for (i in nums.indices) {
            val right = total - left - nums[i]
            ans[i] = kotlin.math.abs(left - right)
            left += nums[i]
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def leftRightDifference(self, nums: list[int]) -> list[int]:
        n = len(nums)
        ans = [0] * n
        total = sum(nums)
        left = 0
        for i, x in enumerate(nums):
            right = total - left - x
            ans[i] = abs(left - right)
            left += x
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn left_right_difference(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut ans = vec![0; n];
        let total: i32 = nums.iter().sum();
        let mut left = 0;
        for (i, &x) in nums.iter().enumerate() {
            let right = total - left - x;
            ans[i] = (left - right).abs();
            left += x;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    leftRightDifference(nums: number[]): number[] {
        const n = nums.length;
        const ans = new Array(n).fill(0);
        let total = nums.reduce((a, b) => a + b, 0);
        let left = 0;
        for (let i = 0; i < n; i++) {
            const right = total - left - nums[i];
            ans[i] = Math.abs(left - right);
            left += nums[i];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We traverse the array twice (sum and answer).
  • 🧺 Space complexity: O(n), for the answer array.