Skip to content

2574. Left and Right Sum Differences

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] <= 105

Solutions

Solution 1: Prefix Sum

We define a variable \(left\) to represent the sum of the elements to the left of index \(i\) in the array nums, and a variable \(right\) to represent the sum of the elements to the right of index \(i\) in the array nums. Initially, \(left = 0\), \(right = \sum_{i = 0}^{n - 1} nums[i]\).

We iterate over the array nums. For the current number \(x\) we are iterating over, we update \(right = right - x\). At this point, \(left\) and \(right\) represent the sum of the elements to the left and right of index \(i\) in the array nums, respectively. We add the absolute difference between \(left\) and \(right\) to the answer array ans, and then update \(left = left + x\).

After the iteration is complete, we return the answer array ans.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\). Where \(n\) is the length of the array nums.

Similar problems:

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func leftRigthDifference(nums []int) (ans []int) {
    var left, right int
    for _, x := range nums {
        right += x
    }
    for _, x := range nums {
        right -= x
        ans = append(ans, abs(left-right))
        left += x
    }
    return
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function leftRigthDifference(nums: number[]): number[] {
    let left = 0,
        right = nums.reduce((a, b) => a + b);
    const ans: number[] = [];
    for (const x of nums) {
        right -= x;
        ans.push(Math.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_rigth_difference(nums: Vec<i32>) -> Vec<i32> {
        let mut left = 0;
        let mut right = nums.iter().sum::<i32>();
        nums.iter()
            .map(|v| {
                right -= v;
                let res = (left - right).abs();
                left += v;
                res
            })
            .collect()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* leftRigthDifference(int* nums, int numsSize, int* returnSize) {
    int left = 0;
    int right = 0;
    for (int i = 0; i < numsSize; i++) {
        right += nums[i];
    }
    int* ans = malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++) {
        right -= nums[i];
        ans[i] = abs(left - right);
        left += nums[i];
    }
    *returnSize = numsSize;
    return ans;
}

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function leftRigthDifference(nums: number[]): number[] {
    let left = 0;
    let right = nums.reduce((r, v) => r + v);
    return nums.map(v => {
        right -= v;
        const res = Math.abs(left - right);
        left += v;
        return res;
    });
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn left_right_difference(nums: Vec<i32>) -> Vec<i32> {
        let mut ans = vec![];

        for i in 0..nums.len() {
            let mut left = 0;
            for j in 0..i {
                left += nums[j];
            }

            let mut right = 0;
            for k in i + 1..nums.len() {
                right += nums[k];
            }

            ans.push((left - right).abs());
        }

        ans
    }
}

Solution 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl Solution {
    pub fn left_right_difference(nums: Vec<i32>) -> Vec<i32> {
        let mut left = 0;
        let mut right: i32 = nums.iter().sum();
        let mut ans = vec![];

        for &x in &nums {
            right -= x;
            ans.push((left - right).abs());
            left += x;
        }

        ans
    }
}

Comments