Left and Right Sum Differences

Difficulty: Easy | Acceptance: 88.00% | Paid: No Topics: Array, Prefix Sum

Given a 0-indexed integer array nums, find the difference array answer.

For each index i, answer[i] = |leftSum[i] - rightSum[i]|.

Where:

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

Return the array answer.

• Examples
• Constraints
• Brute Force
• Prefix Sum (Optimal)
• Two Pass Prefix Sum

Examples

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

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

Constraints

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁵

Brute Force

Intuition For each element in the array, we can explicitly calculate the sum of elements to its left and the sum of elements to its right by iterating through the array.

Steps

• Initialize an empty result array.
• Iterate through the array with index i.
• For each i, calculate leftSum by iterating from 0 to i - 1.
• For each i, calculate rightSum by iterating from i + 1 to n - 1.
• Calculate the absolute difference and append it to the result.
• Return the result.

from typing import List

class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = []
        for i in range(n):
            left_sum = 0
            right_sum = 0
            
            # Calculate left sum
            for j in range(i):
                left_sum += nums[j]
                
            # Calculate right sum
            for j in range(i + 1, n):
                right_sum += nums[j]
                
            answer.append(abs(left_sum - right_sum))
            
        return answer

Complexity

• Time: O(n²) - For each element, we iterate through the array to calculate sums.
• Space: O(1) - Excluding the space required for the output array.
• Notes: Simple to implement but inefficient for large arrays.

Prefix Sum (Optimal)

Intuition We can calculate the total sum of the array once. As we iterate through the array, we can maintain a running leftSum. The rightSum for the current index can be derived by subtracting the leftSum and the current element from the total sum.

Steps

• Calculate the total sum of the array.
• Initialize leftSum to 0.
• Iterate through the array.
• For each element nums[i], calculate rightSum = totalSum - leftSum - nums[i].
• Calculate the absolute difference between leftSum and rightSum and store it in the result.
• Add nums[i] to leftSum.
• Return the result.

from typing import List

class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        total_sum = sum(nums)
        left_sum = 0
        answer = []
        
        for n in nums:
            right_sum = total_sum - left_sum - n
            answer.append(abs(left_sum - right_sum))
            left_sum += n
            
        return answer

Complexity

• Time: O(n) - We pass through the array twice (once for total sum, once for the answer).
• Space: O(1) - Excluding the space required for the output array.
• Notes: This is the most efficient approach for this problem.

Two Pass Prefix Sum

Intuition We can pre-compute the prefix sum (sum of elements up to index i) and suffix sum (sum of elements from index i to end) for every index. Then, we can construct the answer array by looking up these pre-computed values.

Steps

• Initialize leftSum array of size n with 0s.
• Initialize rightSum array of size n with 0s.
• Fill leftSum array: leftSum[i] = leftSum[i-1] + nums[i-1].
• Fill rightSum array: rightSum[i] = rightSum[i+1] + nums[i+1].
• Iterate and calculate answer[i] = |leftSum[i] - rightSum[i]|.
• Return answer.

from typing import List

class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left_sum = [0] * n
        right_sum = [0] * n
        
        # Calculate prefix sums
        for i in range(1, n):
            left_sum[i] = left_sum[i-1] + nums[i-1]
            
        # Calculate suffix sums
        for i in range(n - 2, -1, -1):
            right_sum[i] = right_sum[i+1] + nums[i+1]
            
        # Calculate answer
        return [abs(left_sum[i] - right_sum[i]) for i in range(n)]

Complexity

• Time: O(n) - We pass through the array three times (left, right, answer).
• Space: O(n) - We use two extra arrays of size n to store prefix and suffix sums.
• Notes: Uses more memory than the optimal approach but clearly demonstrates the concept of prefix sums.