2574. Left and Right Sum Differences

EasyArrayPrefix Sum
Leetcode Link

Problem Description

The problem presents us with an array of integers called nums. Our goal is to construct another array called answer. The length of answer must be the same as nums. Each element in answer, answer[i], is defined as the absolute difference between the sum of elements to the left and to the right of nums[i]. Specifically,

  • leftSum[i] is the sum of all elements before nums[i] in nums. If i is 0, leftSum[i] is 0 since there are no elements to the left.
  • rightSum[i] is the sum of all elements after nums[i] in nums. If i is at the last index of nums, rightSum[i] becomes 0 since there are no elements after it.

We need to calculate this absolute difference for every index in the nums array and return the resulting array answer.

Intuition

To solve this problem, we look for an efficient way to calculate the left and right sums without repeatedly summing over subsets of the array for each index, which would lead to an inefficient solution with a high time complexity.

We start by observing that for each index i, leftSum[i] is simply the sum of all previous elements in nums up to but not including nums[i], and rightSum[i] is the sum of all elements after nums[i].

We can keep track of the leftSum as we iterate through the array by maintaining a running sum of the elements we've seen so far. Similarly, we'll keep track of the rightSum by starting with the sum of the entire array and subtracting elements as we iterate through the array.

Here's the step by step approach:

  • Initialize left as 0 to represent the initial leftSum (since there are no elements to the left of index 0).
  • Calculate the initial rightSum as the sum of all elements in nums.
  • Traverse each element x in nums from left to right.
  • For each element, calculate the current rightSum by subtracting the value of the current element (x) from rightSum.
  • Calculate the absolute difference between left and rightSum and append it to ans (the answer array).
  • Update left by adding the value of x to include it in the left sum for the next element's computation.
  • Return the answer array after the loop ends.

By doing this, we efficiently compute the required absolute differences, resulting in a linear time complexity solution (i.e., O(n)) - which is optimal given that we need to look at each element at least once.

Learn more about Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search is equivalent to which of the tree traversal order?

Solution Approach

The implementation of the solution follows a straightforward approach using a single pass through the array which uses the two-pointer technique effectively. Here is a breakdown of this approach, including the algorithms, data structures, or patterns used in the solution:

  • Initialize a variable called left to 0. This variable will hold the cumulative sum of elements to the left of the current index i as the array is iterated through.

  • Compute the total sum of all elements in nums and store this in a variable called right. This represents the sum of all elements to the right of the current index i before we start the iteration.

  • Create an empty list called ans that will store the absolute differences between the left and right sums for each index i.

  • Start iterating through each element x in the nums array:

    1. Before we update left, right still includes the value of the current element x. Hence, subtract x from right to update the rightSum for the current index.

    2. Compute the absolute difference between the updated sums left and right as abs(left - right).

    3. Append the computed absolute difference to the ans list.

    4. Add the value of the current element x to left. After this addition, left correctly represents the sum of elements to the left of the next index.

  • At the end of this single pass, all elements in nums have been considered, and ans contains the computed absolute differences.

  • Return the list ans as the solution.

This algorithm is efficient since it traverses the array only once (O(n) time complexity), and uses a constant amount of extra space for the variables left, right, and the output list ans (O(1) space complexity, excluding the output list). It avoids the need for nested loops or recursion, which could result in higher time complexity, by cleverly updating left and right at each step, thereby considering the impact of each element on the leftSum and rightSum without explicitly computing these each time.

Here's how the pseudo-code might look like:

1left = 0
2right = sum(nums)
3ans = []
4
5for x in nums:
6    right -= x
7    ans.append(abs(left - right))
8    left += x
9  
10return ans

Each step progresses logically from understanding the problem to implementing a solution that addresses the problem's requirements efficiently.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example Walkthrough

Let's go through an illustrative example using the array nums = [1, 2, 3, 4]. We will apply the solution approach step by step.

  1. We initialize left to 0 and right is the sum of all elements in nums, which is 1 + 2 + 3 + 4 = 10.

  2. Start with an empty answer array ans = [].

  3. For the first element x = 1:

    • Subtract x from right: right = 10 - 1 = 9.
    • Calculate the absolute difference abs(left - right) = abs(0 - 9) = 9 and append to ans: ans = [9].
    • Add x to left: left = 0 + 1 = 1.

  4. For the second element x = 2:

    • Subtract x from right: right = 9 - 2 = 7.
    • Calculate the absolute difference abs(left - right) = abs(1 - 7) = 6 and append to ans: ans = [9, 6].
    • Add x to left: left = 1 + 2 = 3.

  5. For the third element x = 3:

    • Subtract x from right: right = 7 - 3 = 4.
    • Calculate the absolute difference abs(left - right) = abs(3 - 4) = 1 and append to ans: ans = [9, 6, 1].
    • Add x to left: left = 3 + 3 = 6.

  6. For the fourth and final element x = 4:

    • Subtract x from right: right = 4 - 4 = 0.
    • Calculate the absolute difference abs(left - right) = abs(6 - 0) = 6 and append to ans: ans = [9, 6, 1, 6].
    • left would be updated, but since this is the last element it's not necessary for the calculation.

  7. The iteration is complete, and the answer array ans is [9, 6, 1, 6].

This array represents the absolute differences between the sum of elements to the left and to the right for each element in nums. The algorithm has linear time complexity, O(n), where n is the number of elements in nums, because it processes each element of the array exactly once.

Solution Implementation

1from typing import List
2
3class Solution:
4    def leftRightDifference(self, nums: List[int]) -> List[int]:
5        # Initialize left sum as 0 and right sum as the sum of all elements in nums
6        left_sum, right_sum = 0, sum(nums)
7
8        # This list will store the absolute differences
9        result = []
10
11        # Iterate through numbers in nums
12        for num in nums:
13            # Subtract current number from the right sum (as it is moving to the left)
14            right_sum -= num
15
16            # Append the absolute difference between left_sum and right_sum
17            result.append(abs(left_sum - right_sum))
18
19            # Add the current number to the left sum (as it moved from right to left)
20            left_sum += num
21      
22        # Return the result list containing absolute differences
23        return result
24
1import java.util.Arrays; // Import Arrays class to use the stream method
2
3class Solution {
4    // Method to find the absolute difference between the sum of numbers to the left 
5    // and the sum of numbers to the right of each index in an array
6    public int[] leftRightDifference(int[] nums) {
7        int leftSum = 0; // Initialize sum of left numbers
8        int rightSum = Arrays.stream(nums).sum(); // Initialize sum of right numbers using stream
9        int n = nums.length;
10        int[] differences = new int[n]; // Array to store the differences at each position
11
12        // Iterate through the array elements
13        for (int i = 0; i < n; ++i) {
14            rightSum -= nums[i]; // Subtract the current element from the right sum
15            differences[i] = Math.abs(leftSum - rightSum); // Store the absolute difference at the current position
16            leftSum += nums[i]; // Add the current element to the left sum
17        }
18
19        return differences; // Return the array containing the differences
20    }
21}
22
1#include <vector> // Include necessary header for vector
2#include <numeric> // Include numeric header for accumulate function
3
4class Solution {
5public:
6    // Function to calculate the absolute difference between the sum of elements to the left and right
7    // of each element in the array 'nums'
8    vector<int> leftRightDifference(vector<int>& nums) {
9        int leftSum = 0; // Initialize the left sum to 0
10        // Calculate the initial right sum as the total sum of elements in 'nums'
11        int rightSum = accumulate(nums.begin(), nums.end(), 0);
12        vector<int> differences; // Create a vector to store the differences
13
14        // Iterate through each element in the input 'nums' vector
15        for (int num : nums) {
16            rightSum -= num; // Decrement rightSum by the current element value
17            // Calculate the absolute difference between leftSum and rightSum and push to the 'differences' vector
18            differences.push_back(abs(leftSum - rightSum));
19            leftSum += num; // Increment leftSum by the current element value
20        }
21      
22        return differences; // Return the vector containing the differences
23    }
24};
25
1function leftRightDifference(nums: number[]): number[] {
2    // Initialize left sum as 0. It will represent the sum of elements to the left of the current element
3    let leftSum = 0;
4  
5    // Calculate the initial right sum, which is the sum of all elements in the array
6    let rightSum = nums.reduce((total, currentValue) => total + currentValue);
7  
8    // Initialize an empty array to hold the difference between left and right sums at each index
9    const differences: number[] = [];
10  
11    // Iterate over each element in the input array
12    for (const num of nums) {
13        // Subtract the current element from the right sum, since it will now be included in the left sum
14        rightSum -= num;
15      
16        // Calculate the absolute difference between left and right sums and add it to the differences array
17        differences.push(Math.abs(leftSum - rightSum));
18      
19        // Add the current element to the left sum, as we move to the next index
20        leftSum += num;
21    }
22  
23    // Return the array of differences
24    return differences;
25}
26
Not Sure What to Study? Take the 2-min Quiz：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Time and Space Complexity

The given code snippet calculates the absolute difference between the sum of the numbers to the left and right of the current index in an array. Here is the analysis of its computational complexity:

Time Complexity

The time complexity of this code is primarily dictated by the single loop that iterates through the array. It runs for every element of the array nums. Inside the loop, basic arithmetic operations are performed (addition, subtraction, and assignment), which are constant time operations, denoted by O(1). Therefore, the time complexity of the function is O(n), where n is the number of elements in the array nums.

Space Complexity

The space complexity of the code involves both the input and additional space used by the algorithm. The input space for the array nums does not count towards the space complexity of the algorithm. The additional space used by the algorithm is for the variables left, right, and the array ans which stores the result. Since left and right are single variables that use constant space O(1) and the size of ans scales linearly with the size of the input array, the space complexity is O(n) where n is the length of the input array nums.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫