2574. Left and Right Sum Differences - LeetCode Best Solution

Jan 314 min read

Hello Code Recipian! Ready to put your coding skills to the test? Today, let's solve LeetCode problem 2574. Left and Right Sum Differences. Oh, and if you’re on a roll, don’t stop here! This article is part of our epic LeetCode problem solutions series, so be sure to check out the others once you’ve cracked this one.

Alright, let’s dive in and break this problem down! 🔥

Problem Statement: 2574. Left and Right Sum Differences

Given an integer array nums, return an integer array result such that:

result.length == nums.length.
result[i] = |leftSum[i] - rightSum[i]|.

Where:

leftSum[i] is the sum of elements to the left of index i in nums. If there is no such element, leftSum[i] = 0.
rightSum[i] is the sum of elements to the right of index i in nums. If there is no such element, rightSum[i] = 0.

Example 1

Input: nums = [10, 4, 8, 3]

Output: [15, 1, 11, 22]

Justification: leftSum = [0, 10, 14, 22] and rightSum = [15, 11, 3, 0]. Hence, result = [ |0 - 15|, |10 - 11|, |14 - 3|, |22 - 0| ] = [15, 1, 11, 22].

Example 2

Input: nums = [2, 5, 1, 6, 1]

Output: [13, 6, 0, 7, 14]

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 105

Solution: 2574. Left and Right Sum Differences

Brute Force Approach: A naïve way to solve this problem is to use the brute force approach. The brute force approach involves computing leftSum[i] and rightSum[i] separately for each index i in nums array and then calculating the difference between them. However, this results in an O(n²) time complexity, making it impractical for large inputs.

Prefix and Suffix Sum Array Solution: In this approach, instead of re-calculating left and right sum for each index, we store them in leftSum and rightSum arrays. As we traverse through the nums array, we can retrieve the corresponding left and right sums from these arrays to compute the result. While this solution has a time complexity of O(n), it also requires O(n) space due to the use of two additional arrays.

Optimized Prefix Sum Solution: Rather than storing the left and right sums in separate arrays, we can maintain their running sums using two variables leftSum and rightSum. This approach eliminates the need for extra space, optimizing space complexity. The diagram below illustrates how the left and right sums are calculated at a specific index (using index 3 as a reference):

Image showing how left and right sum is calculated

Let's see how this algorithm works in detail.

Algorithm

Calculate total sum:
1. Initialize an integer variable rightSum.
2. Iterate through the nums array and compute the total sum of all elements, store this in rightSum variable.
Compute the result:
1. Initialize an integer variable leftSum to keep track of the running sum of elements to the left of the current element. Initially leftSum is set to 0.
2. Create an array result of size n (length of nums) to store the computed differences.
3. Iterate through the nums array from start to finish. In each iteration perform the following steps:
  1. Update right sum by subtracting the current element from rightSum:
    rightSum = rightSum - nums[i]
  2. Compute the absolute difference between leftSum and rightSum and store it in result[i].
  3. Add the current element to leftSum for the next iteration:
    leftSum = leftSum + nums[i]
4. Repeat these steps for all elements in nums.
Return the result:
Once all elements have been processed, return the result array containing the left and right sum differences.

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

Simulation

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution

Dart Solution

Racket Solution

Complexity Analysis

Time Complexity

Calculating total sum:

The algorithm iterates through the nums array once to calculate rightSum. This takes O(n) time.

Populating the result:

Calculating the difference between leftSum and rightSum and for each element and stroing it in result also requires O(n) time. populating it in result also takes O(n) time since we need to iterate through each element in nums.

Since both steps run in O(n) time, the overall time complexity of this solution is: O(n) + O(n) = O(n).

Space Complexity

The space complexity is O(1) since no extra space is used that depends on the input size, apart from the output array.

Want to master the Prefix Sum pattern? Dive deeper with these must-read articles:

Start exploring now and level up your problem-solving skills!

⚡ FREE Premium Access—Only for a Short Time! ⚡ Love coding? Get expert tutorials, pro tips, and exclusive resources—100% FREE! For a limited time, enjoy full access to Code Recipe Membership at no cost. Don’t wait—grab this deal before time runs out! ⏳ Sign up now!