Skip to main content

Prefix Sum

Left and Right Sum Differences

Problem Description

Given a 0-indexed integer array nums, find a 0-indexed integer array answer where:
1) answer.length == nums.length.
2) answer[i] = |leftSum[i] - rightSum[i]|.

Where:

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

2) rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0.
Return the array answer.

Example

Input: nums = [10,4,8,3]
Output: [15,1,11,22]
Explanation: The array leftSum is [0,10,14,22] and the array rightSum is [15,11,3,0].
The array answer is [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22].

Detailed Explanation

The array leftSum is [0, 10, 14, 22], and the array rightSum is [15, 11, 3, 0].

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

For any index i: answer[i] = absolute(leftSum[i] - rightSum[i])

leftSum[0] = 0
rightSum[0] = nums[1] + nums[2] + nums[3] = 4 + 8 + 3 = 15

Note that the reason why leftSum[0] = 0 is that there are no elements present on the left side of index 0. Hence, leftSum[0] = 0.

leftSum[1] = nums[0] = 10
rightSum[1] = nums[2] + nums[3] = 8 + 3 = 11

leftSum[2] = nums[0] + nums[1] = 10 + 4 = 14
rightSum[2] = nums[3] = 3

leftSum[3] = nums[0] + nums[1] + nums[2] = 10 + 4 + 8 = 22
rightSum[3] = 0

Note: Since there are no elements present on the right side of index 3, rightSum[3] = 0.

Hence,
answer[0] = absolute(leftSum[0] - rightSum[0]) = absolute(0 - 15) = 15
answer[1] = absolute(leftSum[1] - rightSum[1]) = absolute(10 - 11) = 1
answer[2] = absolute(leftSum[2] - rightSum[2]) = absolute(14 - 3) = 11
answer[3] = absolute(leftSum[3] - rightSum[3]) = absolute(22 - 0) = 22

Therefore, answer = [15, 1, 11, 22].

Input: nums = [1]
Output: [0]
Explanation: The array leftSum is [0] and the array rightSum is [0].
The array answer is [|0 - 0|] = [0].

Detailed Explanation

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

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

For any index i :  answer[i] = absolute( leftSum[i] - rightSum[i] )

Hence, answer[0] = absolute( leftSum[0] - rightSum[0] ) = absolute( 0 - 0 ) = 0

Therefore , answer = [0]

 Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^5
💡
Try it Yourself First
As we dive into the brute force approach, our first instinct might be to calculate the sums for each index by repeatedly iterating through the array. This is a very straight forward approach lets see how we do it.

Brute Force Approach


Intuition

In the brute force approach, to calculate the answer[i] for each index i, firstly, we will calculate leftSum[i] by applying the loop from the starting index of the array to index i-1 and will store the sum. Similarly, we will calculate the rightSum[i] by applying the loop from index i+1 to the last index of the array and will store the sum.

So, for a particular index i, we will store both the values, i.e., leftSum[i] and rightSum[i], and at last, to calculate answer[i], we will do the same operation given in the problem.
i.e., answer[i] = absolute(leftSum[i] - rightSum[i]).

We will create two arrays, leftSum and rightSum, of the same size as the nums array where:

  • leftSum[i] = sum of all the elements of the nums array available on the left side of index i.
  • rightSum[i] = sum of all the elements of the nums array available on the right side of index i.

Note: For index 0, leftSum[0] = 0, since no elements are present in the nums array on the left side of index 0. Similarly, for index n-1, rightSum[n-1] = 0, since no elements are present in the nums array on the right side of index n-1 (where n is the size of nums or the input array).

Example

Start traversing in nums array one by one:

For nums[0]:
leftSum[0] = 0 (for index = 0, there will not be any elements on the left side)
rightSum[0] = nums[1] + nums[2] + nums[3] = 4 + 8 + 3 = 15

For nums[1]:
leftSum[1] = nums[0] = 10
rightSum[1] = nums[2] + nums[3] = 8 + 3 = 11

For nums[2]:
leftSum[2] = nums[0] + nums[1] = 10 + 4 = 14
rightSum[2] = nums[3] = 3

For nums[3]:
leftSum[3] = nums[0] + nums[1] + nums[2] = 10 + 4 + 8 = 22
rightSum[3] = 0 (since there is not any element beyond index = 3)

Hence, to calculate the answer array for each element, we will do:
For any index i: answer[i] = absolute(leftSum[i] - rightSum[i])

Hence,
answer[0] = absolute(leftSum[0] - rightSum[0]) = absolute(0 - 15) = 15
answer[1] = absolute(leftSum[1] - rightSum[1]) = absolute(10 - 11) = 1
answer[2] = absolute(leftSum[2] - rightSum[2]) = absolute(14 - 3) = 11
answer[3] = absolute(leftSum[3] - rightSum[3]) = absolute(22 - 0) = 22

Therefore, answer = [15, 1, 11, 22]

Approach

First, we will create two arrays, leftSum and rightSum, of the same size as the nums array. Similarly, we will create one more array named answer that will store the result corresponding to each index.

After that, we will start traversing the nums array, and for every index i:We will calculate the sum of the numbers available on the left side of index i and store it in leftSum[i].Similarly, we will calculate the sum of the numbers available on the right side of index i and store it in rightSum[i].Then, to calculate answer[i], we will use the formula:answer[i] = absolute(leftSum[i] - rightSum[i])

After calculating the answer array, we will output the answer array.

Is it necessary to create the left-sum and right-sum arrays?

We can see that for any particular index i,

First, we calculate the values of left_sum and right_sum and store them in leftSum[i] and rightSum[i], respectively.

We can observe that after calculating the value of left_sum and right_sum, we can directly calculate the value of answer[i]:

answer[i] = absolute(left_sum - right_sum)

This way, we can avoid the extra O(n) space that was used for creating the leftSum and rightSum arrays.

Code for All Languages
C++ 
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Solution function
    vector<int> leftRightDifference(vector<int>& nums) {
        int n = nums.size();  // size of nums array

        // Initialization of and answer array
        vector<int> answer(n);

        // Traverse the nums array to calculate leftsum and rightsum
        for (int i = 0; i < n; i++) {
            int left_sum = 0, right_sum = 0;

            // Loop to calculate the leftsum
            for (int j = 0; j < i; j++)
                left_sum += nums[j];

            // Loop to calculate the rightsum
            for (int j = i + 1; j < n; j++)
                right_sum += nums[j];

           

            // Calculate the answer for index i
            answer[i] = abs(leftsum - rightsum);
        }

        // Return the answer array
        return answer;
    }
};

Java 
import java.util.*;

class Solution {

    // Solution function
    public int[] leftRightDifference(int[] nums) {
        int n = nums.length;  // size of nums array

        //  Initialization of and answer array
       
        int[] answer = new int[n];

        // Traverse the nums array to calculate leftsum and rightsum
        for (int i = 0; i < n; i++) {
            int left_sum = 0;
            int right_sum = 0;

            // Loop to calculate the leftsum
            for (int j = 0; j < i; j++) {
                left_sum += nums[j];
            }

            // Loop to calculate the rightsum
            for (int j = i + 1; j < n; j++) {
                right_sum += nums[j];
            }

           

            // Calculate the answer for index i
            answer[i] = Math.abs(leftsum - rightsum);
        }

        // Return the answer array
        return answer;
    }
}

Python 
class Solution:
    # Solution function
    def leftRightDifference(self, nums):
        n = len(nums)  # size of nums array

        #   Initialization of and answer array

       
        answer = [0] * n

        # Traverse the nums array to calculate leftsum and rightsum
        for i in range(n):
            left_sum = 0
            right_sum = 0

            # Loop to calculate the leftsum
            for j in range(i):
                left_sum += nums[j]

            # Loop to calculate the rightsum
            for j in range(i + 1, n):
                right_sum += nums[j]

           

            # Calculate the answer for index i
            answer[i] = abs(leftsum - rightsum)

        # Return the answer array
        return answer

Javascript 
class Solution {
    // Solution function
    leftRightDifference(nums) {
        const n = nums.length;  // size of nums array

        //  Initialization of and answer array
        const leftsum = Array(n).fill(0);
        const rightsum = Array(n).fill(0);
        const answer = Array(n).fill(0);

        // Traverse the nums array to calculate leftsum and rightsum
        for (let i = 0; i < n; i++) {
            let left_sum = 0;
            let right_sum = 0;

            // Loop to calculate the leftsum
            for (let j = 0; j < i; j++) {
                left_sum += nums[j];
            }

            // Loop to calculate the rightsum
            for (let j = i + 1; j < n; j++) {
                right_sum += nums[j];
            }

          

            // Calculate the answer for index i
            answer[i] = Math.abs(leftsum - rightsum);
        }

        // Return the answer array
        return answer;
    }
}

Time Complexity : O(n²)

The solution contains nested loops that iterate over the array nums to calculate the left and right sums for each element, as well as to store the final results.

Outer Loop (for i from 0 to n-1): This loop runs n times, where n is the size of the input array nums.

Inner Loops:

  • Left sum loop (for j from 0 to i-1): This loop runs i times for each
  • Right sum loop (for j from i+1 to n-1): This loop runs n-i-1 times for each i.

So, for each element in the array nums, we are iterating over all other elements to calculate the left and right sums.

Thus, the time complexity for the entire program is the sum of the time complexities of these loops:

  • The left sum loop runs( 0+1+2+...+(n−1) ) x (0 + 1 + 2 + ... + (n-1) times, which is O(n2).
  • The right sum loop runs ( n−1+n−2+...+0 + n-1 + n-2 + ... + 0 ) x (n−1+n−2+...+0 ) times, which is also O(n2).

The overall time complexity of the solution is: O(n2) + O(n2) = O(n2)

Space Complexity : O(n)

Total Space Complexity:

The code uses several arrays of size n:

  • answer array: Stores the final result for each element in the input array.

Thus, the space complexity due to these arrays is: O(n)

Note that the variables left_sum and right_sum take O(1) space complexity.

Additionally, some auxiliary space is used for integer variables, but that space is constant and does not depend on n. Hence, the overall space complexity is fine.

Therefore, the total space complexity of the code is: O(n)

2. Input Space Complexity : O(n)

The input array nums occupies O(n) space, where n is the number of elements in the array.

So, the input space complexity is: O(n)

3. Auxiliary Space Complexity : O(n)

Auxiliary space refers to the extra space used by the algorithm that is not part of the input space. This includes temporary storage like the answer array.

Since these arrays are of size n, the auxiliary space complexity is: O(n)

In this problem, with constraints up to n = 10³, the brute force approach with O(n²) time complexity (10³ × 10³ = 10⁶) is acceptable, as programming environments typically allow 10⁷ to 10⁸ iterations per second. However, if n increases to 10⁶, the brute force approach (10⁴ × 10⁵ = 10⁹ iterations) will exceed the time limit. This raises the question: can we calculate leftSum[i] and rightSum[i] more efficiently?
The answer is YES!

Optimal Approach

Intuition

Let’s suppose we have to find out the answer[4] and answer[5]. Then to find answer[4] we have to calculate the leftSum[4] and rightSum[4]. Similarly, to calculate answer[5], we have to calculate leftSum[5] and rightSum[5]. By brute force method, we would run a loop to calculate leftSum[4] and rightSum[4]. Similarly, we would again run a loop to calculate leftSum[5] and rightSum[5]. We can observe that we are calculating the sum repeatedly.

For example, to calculate leftSum[4] and leftSum[5], we are calculating the sum from index 0 to index 3 twice. This means we are doing repeated calculations here. Similarly, to calculate rightSum[4] and rightSum[5], we are calculating the sum from index 5 to the last index twice, which results in repeated calculations as well. By noticing this redundancy in calculations, a thought comes into our mind: Could we calculate the sum just once and reuse the previously calculated sum to avoid doing these repeated calculations?

"Is there any way to calculate the sum only once, and instead of calculating the leftSum[i] and rightSum[i] for each index i repeatedly using brute force, can we use the previously calculated sum to compute leftSum[i] and rightSum[i] efficiently?"

Let’s see how we can achieve this : 

Suppose we have given nums array = [ a, b, c,d,e ] of size 5. We have created two different arrays leftsum and rightsum of the same size 5 as the nums array.We are assuming that, LeftSum[i] = sum of elements to the left of the index i in the array nums. If there is no such  element, leftSum[i] = 0. Similarly, rightSum[i] =  sum of elements to the right of the index i in the array nums. If  there is  no such element, rightSum[i] = 0

Since, nums = [a, b, c, d,e] 
Hence,
leftSum = [0, a, a+b, a+b+c, a+b+c+d]
rightSum= [b+c+d+e , c+d+e , d+e , e, 0]

Now, if we want to calculate the answer array for index=3: 

answer[3] = absolute ( (nums[0] + nums[1] + nums[2]) -  (nums[4])  = absolute( a+b+c - e) 

If we carefully observe then we can see that we can get the same answer for answer[3] by applying the below-given operation

answer[3] = absolute ( leftSum[3] -  rightSum[3] )  = absolute (a + b + c - e ) 

Hence we have got the same answer.

Therefore after understanding the proof, we can generalize. For any index i, to calculate the answer[i], we can use the below-given relation:

answer[i] = absolute ( leftSum[i] - rightSum[i] )

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

How to Calculate leftSum and rightSum and answer efficiently?

First of all, we will initialize the values of the leftSum and rightSum arrays with 0.

Now, we will start iterating in the nums array from the 1st index to the last index and store the values of leftSum[i] with leftSum[i-1] + nums[i-1].

Therefore,
leftSum[i] = leftSum[i-1] + nums[i-1]

Similarly,
we will start iterating in the nums array from the second last index to the starting index of the nums array and store the values of rightSum[i] with rightSum[i+1] + nums[i+1].

Therefore,
rightSum[i] = rightSum[i+1] + nums[i+1]

Also, note that leftSum[0] = 0 and rightSum[last_index] = 0 (given in the problem).

To understand this calculation, let’s see sample test case 1, and we will try to calculate the leftSum and rightSum arrays.

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

Let’s create two arrays leftSum and rightSum and initialize them with 0.

leftSum = [0, 0, 0, 0]
rightSum = [0, 0, 0, 0]

For the leftSum array:

For nums[0]:
leftSum[0] = 0 (for index 0, there will not be any elements on the left side)

For nums[1]:
leftSum[1] = nums[0] + leftSum[0] = 10 + 0 = 10

For nums[2]:
leftSum[2] = nums[1] + leftSum[1] = 4 + 10 = 14

For nums[3]:
leftSum[3] = nums[2] + leftSum[2] = 8 + 14 = 22

Hence,
leftSum = [0, 10, 14, 22]

For the rightSum array:

For nums[3]:
rightSum[3] = 0

For nums[2]:
rightSum[2] = nums[3] + rightSum[3] = 3 + 0 = 3

For nums[1]:
rightSum[1] = nums[2] + rightSum[2] = 8 + 3 = 11

For nums[0]:
rightSum[0] = nums[1] + rightSum[1] = 4 + 11 = 15

Hence,
rightSum = [15, 11, 3, 0]

Now, let’s calculate the answer array:

answer[0] = absolute(leftSum[0] - rightSum[0]) = absolute(0 - 15) = 15

answer[1] = absolute(leftSum[1] - rightSum[1]) = absolute(10 - 11) = 1

answer[2] = absolute(leftSum[2] - rightSum[2]) = absolute(14 - 3) = 11

answer[3] = absolute(leftSum[3] - rightSum[3]) = absolute(22 - 0) = 22

Therefore,
answer = [15, 1, 11, 22]

ApproachStep 1: Initialize Arrays
Create three arrays: leftSum, rightSum, and answer, and initialize all their elements to 0.Step 2: Calculate the leftSum Array
Iterate through the leftSum array starting from index 1. For each index i:
leftSum[i] = nums[i-1] + leftSum[i-1]Step 3: Calculate the rightSum Array
Iterate through the rightSum array starting from the second-to-last index to the first index. For each index i:
rightSum[i] = nums[i+1] + rightSum[i+1]Step 4: Calculate the answer Array
Iterate through the array. For each index i:
answer[i] = absolute(leftSum[i] - rightSum[i])Step 5: Return the answer Array
Return the final answer array.Learning TipWe have understood in an array for any particular index i, how we can calculate the sum of numbers present on left and right side efficiently.