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

Start with the direct reading of the question. For each index, add up everything on the left, add up everything on the right, then take the difference. That is correct, but every index costs a full pass over the array, so the total work is N squared.

The saving comes from one fact. The two sums are not independent.

The whole array adds up to a single fixed number. Call it total. Once you know the sum on the left of index i, the sum on the right is already decided:

rightSum = total - leftSum - nums[i]

There is nothing left to add up. You get total from one pass, and you can carry leftSum along as you walk.

So the whole job takes two passes. The first pass adds up total. The second pass walks the array and writes one answer per index.

The shipped code keeps rightSum as a running value rather than recomputing the formula each time. It starts rightSum at total and subtracts the current value before using it. That gives the same number: after the subtraction, rightSum holds everything strictly to the right of i.

Neither pass builds a helper array. Two plain integers carry all the state, so the only memory that grows with the input is the answer itself.

Step-by-step Algorithm

Set leftSum to 0. Set rightSum to the total of the whole array.
Create a differenceArray with the same length as nums.
For each index i from 0 to the end:
- Subtract nums[i] from rightSum. It now holds the sum of everything to the right of i.
- Store |rightSum - leftSum| in differenceArray[i].
- Add nums[i] to leftSum. It now holds the sum of everything to the left of i + 1.
Return differenceArray.

The order inside the loop matters. rightSum drops the current value before the answer is taken, and leftSum picks it up only after, so the current value belongs to neither side.

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

Code

Here is the code for this algorithm:

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

· 16 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