Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Left and Right Sum Differences (easy)

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 leftSum<sup>i</sup>), and subtract it from the sum of all elements to the right of index i in array nums (let's call it rightSum<sup>i</sup>), taking the absolute value of the result:

<center>

.....

.....

.....

Like the course? Get enrolled and start learning!
Lining Wang

Lining Wang

· 3 years ago

The right suffix array doesn't need to be calculated since you can calculate the total of all elements once, subtract the left suffix, and the current element to get the right suffix value.

Show 1 reply
Sahil and Team

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 4 replies
M

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 -

  1. Storing the left/prefix sums in the result array itself
  2. 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 2 replies
Leopoldo Hernandez

Leopoldo Hernandez

· 2 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
T N

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
Exanubes

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 1 reply
T

tranlannhi

· 3 years ago

Why does the illustration for the difference array show [14,12,7,6]? (which is the same as the right sum array)

KP K

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;
    }
}
Othmane Abouelyzza

Othmane Abouelyzza

· 2 years ago

Hello,

the problem statement specifies that 1 <= nums[i] <= 105 but whan I submitted my code, there were test cases with negatives numbers in the nums array.

Gopalrao Yadawadakar

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);
        }