algoadvance

You are given a 0-indexed integer array nums. Determine the array answer of the same length where answer[i] is the absolute difference between the sum of the first i+1 elements and the sum of the elements from i to the end of the array for each element i in the array.

In other words, answer[i] = abs(sum(nums[:i+1]) - sum(nums[i:])).

Return the array answer.

Examples

Example 1:

Input: nums = [10,4,8,3]
Output: [15,1,11,22]
Explanation: The array answer is computed as follows: 
For i = 0: |10 + 4 + 8 + 3| - |_| = |25 - 0| = 25
For i = 1: |10 + 4 + 8 + 3| - |10| = |25 - 10| = 15
For i = 2: |10 + 4 + 8 + 3| - |10 + 4| = |25 - 14| = 11
For i = 3: |10 + 4 + 8 + 3| - |10 + 4 + 8| = |25 - 22| = 3

Example 2:

Input: nums = [1,1,1,1]
Output: [3,2,1,0]
Explanation: The array answer is computed as follows: 
For i = 0: |1 + 1 + 1 + 1| - |_| = |4 - 0| = 4
For i = 1: |1 + 1 + 1 + 1| - |1| = |4 - 1| = 3
For i = 2: |1 + 1 + 1 + 1| - |1 + 1| = |4 - 2| = 2
For i = 3: |1 + 1 + 1 + 1| - |1 + 1 + 1| = |4 - 3| = 1

Constraints

Clarifying Questions

  1. Should the solution consider only non-negative integers in the array?
    • Answer: Yes, since the constraints guarantee 1 <= nums[i].

Code

Strategy

  1. Calculate the Total Sum: First, calculate the total sum of all elements in the array.
  2. Initialize Running Sum: Use a running sum to keep track of the sum of the elements from the start up to the current index.
  3. Calculate the Differences: Iterate through the array, updating the running sum and calculating the difference between the running sum and the sum of the remaining elements.
  4. Store Absolute Values: Store the absolute value of the differences in a new array.

Time Complexity

The time complexity of this solution is O(n) because it processes the array elements in linear time, where n is the number of elements in the array.

Here’s the implementation:

def leftRightDifference(nums):
    total_sum = sum(nums)
    left_sum = 0
    result = []

    for i in range(len(nums)):
        left_sum += nums[i]
        right_sum = total_sum - left_sum
        diff = abs(left_sum - right_sum)
        result.append(diff)
    
    return result

Let’s analyze an example step-by-step.

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

  1. Calculate the total sum: total_sum = 10 + 4 + 8 + 3 = 25
  2. Initialize left_sum = 0
  3. Iterate through the array:
    • For i = 0: left_sum = 10, right_sum = 25 - 10 = 15, diff = 10 - 15 = 5
    • For i = 1: left_sum = 14, right_sum = 25 - 14 = 11, diff = 14 - 11 = 3
    • For i = 2: left_sum = 22, right_sum = 25 - 22 = 3, diff = 22 - 3 = 19
    • For i = 3: left_sum = 25, right_sum = 25 - 25 = 0, diff = 25 - 0 = 25

Result: [15, 5, 11, 22]

Here is the final implementation with an example run:

def leftRightDifference(nums):
    total_sum = sum(nums)
    left_sum = 0
    result = []

    for i in range(len(nums)):
        left_sum += nums[i]
        right_sum = total_sum - left_sum
        diff = abs(left_sum - right_sum)
        result.append(diff)
    
    return result

# Example Run:
nums = [10, 4, 8, 3]
print(leftRightDifference(nums))  # Output: [15, 5, 11, 22]

This solution efficiently calculates the left and right sum differences using linear time complexity.

Try our interview co-pilot at AlgoAdvance.com