Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Solution: 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>

differenceArray[i] = | leftSum<sup>i</sup> - rightSum<sup>i</sup> |

</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
  • 1 <= nums[i] <= 10<sup>5</sup>

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

  1. Initialize variables leftSum and rightSum to 0.
  2. Calculate the total sum of the array and store it in rightSum.
  3. Initialize an array differenceArray to store the differences.
  4. 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.
  5. Return the differenceArray as the result.

Algorithm Walkthrough

Let's consider the Input: nums = [2, 5, 1, 6, 1]

Image

  1. Initialization:

    • leftSum = 0
    • rightSum = 0
    • differenceArray = [0, 0, 0, 0, 0]

  2. Calculate total sum (rightSum):

    • rightSum = 2 + 5 + 1 + 6 + 1 = 15

  3. 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

  4. Return Result:

    • The final differenceArray is [13, 6, 0, 7, 14].

Code

Python3
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(N) due to the space needed for the differenceArray.

Mark as Completed