Problem Description

You are given a 0-indexed integer array nums of size n. Your task is to create a new array where each element represents the absolute difference between the sum of elements to its left and the sum of elements to its right.

For each index i in the array:

• The left sum is the sum of all elements that appear before index i (elements at indices 0 to i-1). If no elements exist to the left, the left sum is 0.
• The right sum is the sum of all elements that appear after index i (elements at indices i+1 to n-1). If no elements exist to the right, the right sum is 0.

Your goal is to return an array answer where answer[i] = |leftSum[i] - rightSum[i]| for each index i.

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

• At index 0: left sum = 0 (no elements to the left), right sum = 4 + 8 + 3 = 15, difference = |0 - 15| = 15
• At index 1: left sum = 10, right sum = 8 + 3 = 11, difference = |10 - 11| = 1
• At index 2: left sum = 10 + 4 = 14, right sum = 3, difference = |14 - 3| = 11
• At index 3: left sum = 10 + 4 + 8 = 22, right sum = 0 (no elements to the right), difference = |22 - 0| = 22

The result would be [15, 1, 11, 22].

Intuition

The key insight is that we don't need to calculate the left and right sums from scratch for each index. Instead, we can maintain running sums that we update as we traverse the array.

Initially, we know that:

• For index 0, the left sum is 0 and the right sum is the total sum minus the first element
• As we move to the next index, the element we just passed becomes part of the left sum, and is no longer part of the right sum

This suggests a sliding window approach where we maintain two variables:

• left: starts at 0 and accumulates elements as we pass them
• right: starts with the total sum of all elements and decreases as we process each element

For each element at index i:

1. First, we remove the current element from right (since the right sum doesn't include the element at index i)
2. Now left and right represent the exact sums we need for this index
3. We calculate |left - right| and add it to our answer
4. Finally, we add the current element to left (preparing for the next iteration)

This way, we only need a single pass through the array with constant time operations at each step, avoiding the need to recalculate sums repeatedly. The pattern of "subtract from right, calculate difference, add to left" elegantly handles the transition from one index to the next.

Learn more about Prefix Sum patterns.

Solution Approach

We implement the solution using a prefix sum technique with two running counters:

1. Initialize variables:

   • left = 0: Tracks the sum of elements to the left of the current index
   • right = sum(nums): Initially holds the total sum of all elements
   • ans = []: Stores the result array

2. Single pass iteration: For each element x in nums:

   a. Update right sum: right -= x

   • This removes the current element from the right sum since the right sum for index i should not include nums[i]

   b. Calculate and store the difference: ans.append(abs(left - right))

   • At this point, left contains the sum of all elements before index i
   • And right contains the sum of all elements after index i
   • We compute the absolute difference and add it to our answer

   c. Update left sum: left += x

   • Add the current element to the left sum, preparing for the next iteration

3. Return the result: After processing all elements, return ans

Example walkthrough with nums = [10, 4, 8, 3]:

• Initial: left = 0, right = 25, ans = []
• Index 0 (x = 10): right = 25 - 10 = 15, append |0 - 15| = 15, left = 0 + 10 = 10
• Index 1 (x = 4): right = 15 - 4 = 11, append |10 - 11| = 1, left = 10 + 4 = 14
• Index 2 (x = 8): right = 11 - 8 = 3, append |14 - 3| = 11, left = 14 + 8 = 22
• Index 3 (x = 3): right = 3 - 3 = 0, append |22 - 0| = 22, left = 22 + 3 = 25
• Result: [15, 1, 11, 22]

The time complexity is O(n) as we traverse the array once, and the space complexity is O(1) if we don't count the output array.

Example Walkthrough

Let's walk through the solution with nums = [2, 5, 1]:

Initial Setup:

• Calculate total sum: 2 + 5 + 1 = 8
• Initialize: left = 0, right = 8, ans = []

Processing Index 0 (value = 2):

1. Update right sum: right = 8 - 2 = 6 (remove current element from right)
2. Calculate difference: |left - right| = |0 - 6| = 6
3. Add to answer: ans = [6]
4. Update left sum: left = 0 + 2 = 2 (add current element to left)

Processing Index 1 (value = 5):

1. Update right sum: right = 6 - 5 = 1 (remove current element from right)
2. Calculate difference: |left - right| = |2 - 1| = 1
3. Add to answer: ans = [6, 1]
4. Update left sum: left = 2 + 5 = 7 (add current element to left)

Processing Index 2 (value = 1):

1. Update right sum: right = 1 - 1 = 0 (remove current element from right)
2. Calculate difference: |left - right| = |7 - 0| = 7
3. Add to answer: ans = [6, 1, 7]
4. Update left sum: left = 7 + 1 = 8 (add current element to left)

Final Result: [6, 1, 7]

The key pattern to observe is how we maintain the invariant that at each step, after subtracting the current element from right, we have exactly the sums we need to calculate the difference for that index. This eliminates redundant calculations and gives us an efficient O(n) solution.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

• The initial sum(nums) operation takes O(n) time to traverse through all elements
• The for loop iterates through each element in nums exactly once, performing constant time operations (O(1)) in each iteration: subtraction, absolute value calculation, append operation, and addition
• Total time complexity: O(n) + O(n) = O(n)

Space Complexity: O(n)

• The algorithm uses O(1) extra space for variables left and right
• The ans list stores exactly n elements (one for each element in nums), requiring O(n) space
• Since the output array is typically required for the problem and counts toward space complexity, the total space complexity is O(n)
• If we don't count the output array (as some analyses do), the auxiliary space complexity would be O(1)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Order of Operations

A common mistake is updating the left_sum before calculating the difference, or forgetting to update right_sum before the calculation. This leads to incorrect results because the sums would include or exclude the wrong elements.

Incorrect Implementation:

def leftRightDifference(self, nums: List[int]) -> List[int]:
    left_sum = 0
    right_sum = sum(nums)
    result = []
  
    for num in nums:
        left_sum += num  # ❌ Updated too early!
        right_sum -= num
        result.append(abs(left_sum - right_sum))
  
    return result

Why it's wrong: For index i, left_sum should contain the sum of elements before index i, not including nums[i]. By adding num to left_sum before calculating the difference, we're including the current element in the left sum, which violates the problem requirements.

Correct Order:

1. First, subtract current element from right_sum
2. Then, calculate the difference
3. Finally, add current element to left_sum

2. Typo in Method Name

The provided code has a typo: leftRigthDifference instead of leftRightDifference. This will cause the solution to fail on submission platforms that expect exact method names.

Fix:

def leftRightDifference(self, nums: List[int]) -> List[int]:  # Note the spelling correction

3. Not Handling Edge Cases Mentally

While the code handles single-element arrays correctly, developers might overthink and add unnecessary special case handling:

Unnecessary complexity:

def leftRightDifference(self, nums: List[int]) -> List[int]:
    if len(nums) == 1:  # ❌ Unnecessary special case
        return [0]
  
    # rest of the code...

The algorithm naturally handles this case: for a single element, left_sum = 0 and right_sum = 0 after subtraction, giving |0 - 0| = 0.

4. Using Two Passes When One Suffices

Some might calculate prefix and suffix sums in separate passes:

Inefficient approach:

def leftRightDifference(self, nums: List[int]) -> List[int]:
    n = len(nums)
    left_sums = [0] * n
    right_sums = [0] * n
  
    # First pass for left sums
    for i in range(1, n):
        left_sums[i] = left_sums[i-1] + nums[i-1]
  
    # Second pass for right sums
    for i in range(n-2, -1, -1):
        right_sums[i] = right_sums[i+1] + nums[i+1]
  
    # Third pass for differences
    return [abs(left_sums[i] - right_sums[i]) for i in range(n)]

While correct, this uses O(n) extra space and multiple passes. The single-pass solution with running counters is more elegant and space-efficient.