LeetCode 2574. Left and Right Sum Differences Solution in Java, C++, Python & More | Explanation + Code

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 l to represent the sum of elements to the left of index i in the array nums, and a variable r to represent the sum of elements to the right of index i in the array nums. Initially, l = 0, r = ∑_{i = 0}^{n - 1} nums[i].

We traverse the array nums. For the current number x, we update r = r - x. At this point, l and r represent the sum of elements to the left and right of index i in the array nums, respectively. We add the absolute difference of l and r to the answer array ans, then update l = l + x.

After the traversal, we return the answer array ans.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1), not counting the space for the return value.

Similar problems:

• 0724. Find Pivot Index
• 1991. Find the Middle Index in Array

PythonJavaC++GoTypeScriptRustC

class Solution: def leftRightDifference(self, nums: List[int]) -> List[int]: l, r = 0, sum(nums) ans = [] for x in nums: r -= x ans.append(abs(l - r)) l += x return ans(code-box)

class Solution { public int[] leftRightDifference(int[] nums) { int l = 0, r = 0; for (int x : nums) { r += x; } int n = nums.length; int[] ans = new int[n]; for (int i = 0; i < n; ++i) { r -= nums[i]; ans[i] = Math.abs(l - r); l += nums[i]; } return ans; } }(code-box)

class Solution { public: vector<int> leftRightDifference(vector<int>& nums) { int l = 0, r = 0; for (int x : nums) { r += x; } int n = nums.size(); vector<int> ans(n); for (int i = 0; i < n; ++i) { r -= nums[i]; ans[i] = abs(l - r); l += nums[i]; } return ans; } };(code-box)

func leftRightDifference(nums []int) []int { l, r := 0, 0 for _, x := range nums { r += x } n := len(nums) ans := make([]int, n) for i, x := range nums { r -= x ans[i] = abs(l - r) l += x } return ans } func abs(x int) int { if x < 0 { return -x } return x }(code-box)

function leftRightDifference(nums: number[]): number[] { let [l, r] = [0, nums.reduce((a, b) => a + b, 0)]; const ans: number[] = []; for (const x of nums) { r -= x; ans.push(Math.abs(l - r)); l += x; } return ans; }(code-box)

impl Solution { pub fn left_right_difference(nums: Vec<i32>) -> Vec<i32> { let mut l = 0; let mut r: i32 = nums.iter().sum(); let mut ans = Vec::with_capacity(nums.len()); for x in nums { r -= x; ans.push((l - r).abs()); l += x; } ans } }(code-box)

/** * Note: The returned array must be malloced, assume caller calls free(). */ int* leftRightDifference(int* nums, int numsSize, int* returnSize) { *returnSize = numsSize; int* ans = (int*) malloc(sizeof(int) * numsSize); int l = 0, r = 0; for (int i = 0; i < numsSize; ++i) { r += nums[i]; } for (int i = 0; i < numsSize; ++i) { r -= nums[i]; ans[i] = abs(l - r); l += nums[i]; } return ans; }(code-box)