Grokking Data Structures & Algorithms for Coding Interviews

0% completed

Solution: Left and Right Sum Differences (easy)

On This Page

Problem Statement

Examples

Why this is a Prefix Sum problem

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

Problem Statement

Given an input array of integers nums, find an integer array, let's call it differenceArray, of the same length as an input integer array.

Each element of differenceArray, i.e., differenceArray[i], should be calculated as follows: take the sum of all elements to the left of index i in array nums (let's call it leftSumi), and subtract it from the sum of all elements to the right of index i in array nums (let's call it rightSumi), taking the absolute value of the result:

differenceArray[i] = | leftSumi - rightSumi |

</center>

If there are no elements to the left or right of i, the corresponding sum should be taken as 0.

Examples

Example 1:

Input: nums = [2, 5, 1, 6, 1]
Expected Output: [13, 6, 0, 7, 14]
Explanation:
- For i=0: |(0) - (5+1+6+1)| = |0 - 13| = 13
- For i=1: |(2) - (1+6+1)| = |2 - 8| = 6
- For i=2: |(2+5) - (6+1)| = |7 - 7| = 0
- For i=3: |(2+5+1) - (1)| = |8 - 1| = 7
- For i=4: |(2+5+1+6) - (0)| = |14 - 0| = 14

Example 2:

Input: nums = [3, 3, 3]
Expected Output: [6, 0, 6]
Explanation:
- For i=0: |(0) - (3+3)| = 6
- For i=1: |(3) - (3)| = 0
- For i=2: |(3+3) - (0)| = 6

Example 3:

Input: nums = [1, 2, 3, 4, 5]
Expected Output: [14, 11, 6, 1, 10]
Explanation:
- Calculations for each index i will follow the above-mentioned logic.

Constraints:

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

Why this is a Prefix Sum problem

What the question says	The signal it matches
"take the sum of all elements to the left of index i"	the wording mentions a running total
"subtract it from the sum of all elements to the right of index i"	the total on the left is compared with the total on the right

This is the compare two sides variant: the total on the left against the total on the right.

The closest alternative. There is none. This is Find the Middle Index reporting a value at every position instead of stopping at the first balance point.

That makes it the clearest statement of the pattern in the chapter. The same two running totals answer both questions, and only the output differs. One returns an index where the difference is zero. The other returns the difference itself everywhere. Note the absolute value in the formula, so the sign of the difference never appears in the answer. The ends use 0 for the missing side, exactly as before.

Solution

To solve this problem, we use a two-pass approach. First, we calculate the total sum of the array. Then, we iterate through the array to compute the absolute difference between the sum of elements to the left and the sum of elements to the right for each position. This is done efficiently using two variables: leftSum to keep track of the sum of elements to the left and rightSum to keep track of the sum of elements to the right. As we traverse the array, we update these sums and calculate the differences. This ensures that the solution runs in linear time, making it efficient for large inputs.

Step-by-step Algorithm

Initialize variables leftSum and rightSum to 0.
Calculate the total sum of the array and store it in rightSum.
Initialize an array differenceArray to store the differences.
Iterate through the array nums:
- Subtract the current element from rightSum.
- Calculate the absolute difference between rightSum and leftSum and store it in differenceArray at the current index.
- Add the current element to leftSum.
Return the differenceArray as the result.

Algorithm Walkthrough

Everything to the left adds up to 0 and everything to the right adds up to 13, so the answer at index 0 is |0 - 13| = 13

1 of 6

Initialization:
- leftSum = 0
- rightSum = 0
- differenceArray = [0, 0, 0, 0, 0]
Calculate total sum (rightSum):
- rightSum = 2 + 5 + 1 + 6 + 1 = 15
Calculate differences:
- Iteration 1 (i = 0):
  - Current number: nums[0] = 2
  - Subtract nums[0] from rightSum: rightSum = 15 - 2 = 13
  - Calculate difference: |rightSum - leftSum| = |13 - 0| = 13
  - Store difference in differenceArray[0]: differenceArray = [13, 0, 0, 0, 0]
  - Add nums[0] to leftSum: leftSum = 0 + 2 = 2
- Iteration 2 (i = 1):
  - Current number: nums[1] = 5
  - Subtract nums[1] from rightSum: rightSum = 13 - 5 = 8
  - Calculate difference: |rightSum - leftSum| = |8 - 2| = 6
  - Store difference in differenceArray[1]: differenceArray = [13, 6, 0, 0, 0]
  - Add nums[1] to leftSum: leftSum = 2 + 5 = 7
- Iteration 3 (i = 2):
  - Current number: nums[2] = 1
  - Subtract nums[2] from rightSum: rightSum = 8 - 1 = 7
  - Calculate difference: |rightSum - leftSum| = |7 - 7| = 0
  - Store difference in differenceArray[2]: differenceArray = [13, 6, 0, 0, 0]
  - Add nums[2] to leftSum: leftSum = 7 + 1 = 8
- Iteration 4 (i = 3):
  - Current number: nums[3] = 6
  - Subtract nums[3] from rightSum: rightSum = 7 - 6 = 1
  - Calculate difference: |rightSum - leftSum| = |1 - 8| = 7
  - Store difference in differenceArray[3]: differenceArray = [13, 6, 0, 7, 0]
  - Add nums[3] to leftSum: leftSum = 8 + 6 = 14
- Iteration 5 (i = 4):
  - Current number: nums[4] = 1
  - Subtract nums[4] from rightSum: rightSum = 1 - 1 = 0
  - Calculate difference: |rightSum - leftSum| = |0 - 14| = 14
  - Store difference in differenceArray[4]: differenceArray = [13, 6, 0, 7, 14]
  - Add nums[4] to leftSum: leftSum = 14 + 1 = 15
Return Result:
- The final differenceArray is [13, 6, 0, 7, 14].

Code

Python3

. . . .

Complexity Analysis

Time Complexity

First loop (calculating rightSum): The first loop iterates through the entire array to calculate the total sum (rightSum). This takes $O(N)$ time, where N is the number of elements in the array.
Second loop (calculating differenceArray): The second loop iterates through the array again to calculate the difference between leftSum and rightSum for each index. This also takes $O(N)$ time.
Since both loops run sequentially, the total time complexity is $O(N + N) = O(N)$ .

Overall time complexity: $O(N)$ .

Space Complexity

Difference array: The algorithm creates an additional array differenceArray of size N to store the result. This array requires $O(N)$ space.
Additional variables: The algorithm uses a few extra variables (leftSum, rightSum), which require constant space, $O(1)$ .

Overall space complexity: $O(1)$ extra space, plus the $O(N)$ output array. The differenceArray is the answer we return, so we do not count it as extra space.

Mark as Completed

Shubham Pokale

· 7 days ago

Time complexity of this solution is O(n) and space complexity is O(n) as we need to create the difference array based on input size n.  

    def findDifferenceArray(self, nums):
        n = len(nums)
        differenceArray = [0] * n
        # TODO: Write your code here
        for i in range(n):
            left_sum = sum(nums[:i])
            right_sum = sum(nums[i+1:])
            differenceArray[i] = abs(left_sum - right_sum)
            
        return differenceArray

Show 1 reply

Ravat Tailor

· a year ago

Explanation:

Calculate prefix sum with give that leftSum = 0 so prefixSum[0] = 0
Calculate suffix sum with given that right sum = 0 so suffixSum[n-1] = 0
Calculate the difference between prefixSum and suffixSum array
time and space complexity O(n)

public int[] findDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] differenceArray = new int[n];
        int[] prefixSum = new int[n];
        int[] suffixSum = new int[n];
        prefixSum[0] = 0;
        suffixSum[n-1] = 0;
        for(int i = 1; i< n; i++) {
            prefixSum[i] = prefixSum[i-1] + nums[i-1]; 
        }

        
        for(int i = n-2; i>= 0; i--) {
            suffixSum[i] = suffixSum[i+1] + nums[i+1]; 
        }
        
        for(int i =0;i<n;i++) {
            diffe

Show 1 reply

Gopalrao Yadawadakar

· 2 years ago

 int leftIndicesSum=0,rightIndicesSum=0,totalSum= nums.Sum();
        differenceArray[0] = Math.Abs(nums[0] - totalSum);

        for(int index=1;index <= nums.Length -1;index++)
        {
            leftIndicesSum += nums[index-1];
            rightIndicesSum = totalSum - leftIndicesSum - nums[index];
            differenceArray[index] = Math.Abs(leftIndicesSum - rightIndicesSum);
        }

Show 1 reply

Othmane Abouelyzza

· 2 years ago

Show 1 reply

KP K

· 2 years ago

using System;

public class Solution {
    public int[] findDifferenceArray(int[] nums) {
        int n = nums.Length;
        int[] differenceArray = new int[n];
        int ls=0, rs=0;
        for(int i=0;i<nums.Length;i++){
            rs+=nums[i];
        }
        for(int i=0;i<nums.Length;i++){
            rs-=nums[i];
            differenceArray[i]=Math.Abs(rs-ls);
            ls+=nums[i];
        }
        return differenceArray;
    }
}

Show 1 reply

T N

· 2 years ago

The solution to the problem is not very efficient nor helpful. Why is there O(n) extra space? It's like the monotonic stack pattern.

Typically result space is not calculated in the Big O, so that's why res is not included as space complexity. You can note this to your interviewer if anyone isn't onboard.

    def leftRightDifference(self, nums: List[int]) -> List[int]:
        
        leftsum, rightsum, res = 0, sum(nums), []
        for n in nums:
            rightsum -= n
            res.append(abs(leftsum - rightsum))
            leftsum += n
        return res

Show 1 reply

Exanubes

· 2 years ago

class Solution {
    findDifferenceArray(nums) {
        const n = nums.length;
        const differenceArray = new Array(n).fill(0);
        let right = nums.reduce((acc,curr)=>acc+curr, 0)
        let left = 0;
        for(let i = 0; i<nums.length; i++) {
            right-= nums[i]
            differenceArray[i] = Math.abs(left - right);
            left+= nums[i]
        }
        // TODO: Write your code here
        return differenceArray;
    }
}

I think we can just sum all the numbers and then iteratively subtract from right and add to left. The solution is done in two passes instead of three and saves space by not creating additional arrays for left and right. It's less complicated too

Show 2 replies

Leopoldo Hernandez

· 3 years ago

"""
My solution:
Time Complexity:
The time complexity is O(n),
where n is the length of the input list nums.
The function iterates through the list twice: once to calculate the total sum (total),
and once to calculate the difference array.
Space Complexity:
The space complexity is O(n).
The differenceArray list is of the same length as nums,
and additional variables (total, left, right, diff_total, el) use constant space.
"""
class Solution:
    def findDifferenceArray(self, nums):
        n = len(nums)
        differenceArray = [0] * n

        total = 0
        for el in nums:
            total += el

        left = 0
        for idx, el in enumerate(nums):
            left += el
            right = total - left
            diff_total = (left - el) - right
            differenc

Show 1 reply

Sahil and Team

· 3 years ago

Could be done in more optimised way by storing total sum and calculating rsum & lsum at runtime using total sum. 

    public int[] findDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] differenceArray = new int[n];
        // TODO: Write your code here
        int sum=0,lsum=0;
        for (int i : nums){
          sum+=i;
        }

        for(int i=0;i<nums.length;i++){
          int rsum = sum-nums[i]-lsum;
          differenceArray[i]=Math.abs(rsum-lsum);
          lsum+=nums[i];
        }
        return differenceArray;
    }

Show 5 replies

Manish Giri

· 3 years ago

In the presented solution, you are creating and storing two additional arrays, for storing the prefix and suffix sums. For a brute force solution, this is fine but you should provide an optimized version. It's disappointing that such a solution is not given.

There is no need to create additional arrays that cause O(n) space complexity. This can be done in O(1) space by -

Storing the left/prefix sums in the result array itself
Use an int variable to hold the right/suffix sum and manipulate the result array itself.

Solution -

public class Solution {
    public int[] findDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] differenceArray = new int[n];
        int currLeftSum = 0;
        for(int i = 0; i < n; i++) {
            if(i == 0) {

Show 3 replies

Reading Progress

Vote for new content

On This Page

Problem Statement

Examples

Why this is a Prefix Sum problem

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity