LeetCode 2574 - Left and Right Sum Differences

Difficulty: 🟢 Easy
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem asks us to compute the absolute difference between the sum of elements to the left and the sum of elements to the right for each element in a given array nums. In other words, for every index i, we want to know how different the sums on either side of that index are. The input is a 0-indexed array of integers, where each element is at least 1 and at most 100,000, and the array can have up to 1,000 elements. The output should be an array of the same length where each element is the absolute value of leftSum[i] - rightSum[i].

Key observations include that the first element will always have a leftSum of 0, and the last element will always have a rightSum of 0. Edge cases include arrays of length 1, where both left and right sums are zero, and arrays where all elements are equal or very large, testing numeric limits and sum correctness.

Approaches

The brute-force approach involves computing leftSum[i] and rightSum[i] separately for each index i by iterating over the relevant subarrays. This is correct but inefficient, as for each index we would traverse the array twice in the worst case, resulting in a time complexity of $O(n^2)$, which is acceptable for small arrays but inefficient as n approaches 1000.

The optimal approach uses prefix sums and a running total. Instead of recomputing sums repeatedly, we first compute the total sum of the array. Then we maintain a running leftSum as we iterate through the array. For each element, the rightSum can be calculated as totalSum - leftSum - nums[i], and the absolute difference is straightforward to compute. This reduces the time complexity to $O(n)$ while using only $O(1)$ extra space beyond the output array.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Compute left and right sums separately for each index
Optimal	O(n)	O(1)	Use running left sum and total sum to compute right sum on the fly

Algorithm Walkthrough

Compute the total sum of the array nums. This allows us to derive rightSum[i] at any index without recomputing.
Initialize leftSum to 0. This will accumulate the sum of elements as we iterate from left to right.
Create an output array answer of the same length as nums.
Iterate through each index i of nums:
Compute rightSum[i] as totalSum - leftSum - nums[i].
Compute the absolute difference |leftSum - rightSum[i]| and assign it to answer[i].
Update leftSum by adding nums[i] to it for the next iteration.
Return the answer array.

Why it works: By maintaining a running leftSum and deriving rightSum from the total sum, we avoid repeated summation operations. This ensures that each index's computation is done in constant time, guaranteeing correctness and efficiency.

Python Solution

from typing import List

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

In this Python implementation, we first calculate the total_sum of all elements. We initialize left_sum to zero and iterate over each number, calculating right_sum on the fly and appending the absolute difference to the answer list. Finally, we update left_sum for the next iteration.

Go Solution

func leftRightDifference(nums []int) []int {
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }

    leftSum := 0
    answer := make([]int, len(nums))
    
    for i, num := range nums {
        rightSum := totalSum - leftSum - num
        if leftSum > rightSum {
            answer[i] = leftSum - rightSum
        } else {
            answer[i] = rightSum - leftSum
        }
        leftSum += num
    }

    return answer
}

The Go solution mirrors the Python approach. We compute totalSum first, initialize leftSum to zero, and iterate over the array. The absolute difference is computed using a conditional since Go does not have a built-in abs function for integers. We update leftSum in each iteration and return the result slice.

Worked Examples

Example 1: nums = [10, 4, 8, 3]

|---|---|---|---|---|

| 0 | 10 | 0 | 15 | 15 |

| 1 | 4 | 10 | 11 | 1 |

| 2 | 8 | 14 | 3 | 11 |

| 3 | 3 | 22 | 0 | 22 |

Example 2: nums = [1]

|---|---|---|---|---|

| 0 | 1 | 0 | 0 | 0 |

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the array once to compute `totalSum` and once more to fill the answer array
Space	O(1)	We use a constant amount of extra space besides the output array

The complexity is linear in the size of the input array. Space usage is minimal since we avoid storing separate left and right sums arrays.

Test Cases

# Basic examples
assert Solution().leftRightDifference([10,4,8,3]) == [15,1,11,22]  # from problem
assert Solution().leftRightDifference([1]) == [0]                 # single element

# Edge cases
assert Solution().leftRightDifference([1,1,1,1]) == [3,1,1,3]     # all elements equal
assert Solution().leftRightDifference([100000]) == [0]            # max element, single element
assert Solution().leftRightDifference([1,2,3,4,5]) == [14,9,5,3,10]  # increasing sequence
assert Solution().leftRightDifference([5,4,3,2,1]) == [10,5,3,1,14]  # decreasing sequence

Test	Why
[10,4,8,3]	Standard example from problem statement
[1]	Single element edge case
[1,1,1,1]	All elements equal, tests symmetry
[100000]	Maximum element value, single element
[1,2,3,4,5]	Increasing sequence, tests general behavior
[5,4,3,2,1]	Decreasing sequence, tests general behavior

Edge Cases

Single-element array: The only element has no left or right neighbors, so the difference is 0. Both Python and Go implementations handle this naturally by initializing sums to zero.

All elements equal: This tests whether the code correctly computes sums when left and right sums are identical for inner elements. Our running sum approach handles this efficiently without error.

Large numbers near 100,000: The sum of large numbers could reach 100,000 * 1,000 = 100,000,000, which is well within Python integer limits but requires careful handling in statically typed languages like Go. Using int in Go is safe since typical Go int is at least 32 bits, and sums up to 100 million are safe.