easy Problem 3 Left and Right Sum Differences

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

differenceArray[i] = | leftSumⁱ - rightSumⁱ |

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⁵

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

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

import java.util.Arrays;

public class Solution {

  public int[] findDifferenceArray(int[] nums) {
    int n = nums.length;
    int[] differenceArray = new int[n];
    int leftSum = 0,
      rightSum = 0;

    // Calculate the total sum of the array
    for (int i = 0; i < nums.length; i++) {
      rightSum += nums[i];
    }

    // Calculate the difference between left and right sums for each position
    for (int i = 0; i < nums.length; i++) {
      rightSum -= nums[i];
      differenceArray[i] = Math.abs(rightSum - leftSum);
      leftSum += nums[i];
    }

    return differenceArray;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    int[] example1 = { 2, 5, 1, 6, 1 };
    int[] example2 = { 3, 3, 3 };
    int[] example3 = { 1, 2, 3, 4, 5 };

    System.out.println(Arrays.toString(solution.findDifferenceArray(example1))); // Output: [13, 6, 0, 7, 14]
    System.out.println(Arrays.toString(solution.findDifferenceArray(example2))); // Output: [6, 0, 6]
    System.out.println(Arrays.toString(solution.findDifferenceArray(example3))); // Output: [14, 11, 6, 1, 10]
  }
}

Complexity Analysis

Time Complexity

• First loop (calculating rightSum): The first loop iterates through the entire array to calculate the total sum (rightSum). This takes 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 time.

• Since both loops run sequentially, the total time complexity is .

Overall time complexity: .

Space Complexity

• Difference array: The algorithm creates an additional array differenceArray of size N to store the result. This array requires space.

• Additional variables: The algorithm uses a few extra variables (leftSum, rightSum), which require constant space, .

Overall space complexity: due to the space needed for the differenceArray.