#2574

Easy

LeetCode Problem Workspace

Left and Right Sum Differences

Compute absolute differences between left and right cumulative sums for each element in an integer array efficiently.

Problem Statement

Given a 0-indexed integer array nums of size n, compute the leftSum and rightSum for each position. leftSum[i] is the sum of all elements before index i, and rightSum[i] is the sum of all elements after index i.

Return an integer array answer of size n where answer[i] equals the absolute difference |leftSum[i] - rightSum[i]| for each index. Implement this efficiently using prefix sum techniques to avoid repeated summation.

Examples

Example 1

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

Output: [15,1,11,22]

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

Example 2

Input: nums = [1]

Output: [0]

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] <= 105

Solution Approach

Compute Prefix Sums from Left

Iterate through nums from left to right, maintaining a running sum to fill leftSum. This allows constant-time access to the sum of all elements before each index, avoiding recomputation for each i.

Compute Prefix Sums from Right

Iterate through nums from right to left, maintaining a running sum to fill rightSum. This ensures you can quickly compute the sum of all elements after each index, complementing the leftSum array.

Calculate Absolute Differences

For each index i, subtract rightSum[i] from leftSum[i] and take the absolute value to populate answer[i]. This step directly solves the left and right sum differences pattern efficiently in a single pass.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) due to single traversal for left and right sums. Space complexity is O(n) if separate arrays for leftSum and rightSum are maintained; it can be reduced to O(1) using in-place computation.

What Interviewers Usually Probe

Do you know how to compute cumulative sums without nested loops?
Can you optimize to avoid recalculating sums for each index?
How would you reduce space usage if extra arrays are not allowed?

Common Pitfalls or Variants

Common pitfalls

Forgetting that leftSum[i] excludes nums[i] itself, leading to off-by-one errors.
Recomputing sums inside the loop, resulting in O(n^2) time instead of linear.
Mixing up the direction for rightSum and computing it incorrectly.

Follow-up variants

Compute the difference between left and right product instead of sum for each index.
Find maximum absolute left-right sum difference instead of returning the full array.
Apply the same technique to a 2D matrix row-wise and column-wise for cumulative differences.

FAQ

What is the main idea behind left and right sum differences?

Compute prefix sums from both directions and take the absolute difference at each index to solve efficiently.

Can I solve this problem without extra arrays?

Yes, by maintaining running totals for left and right sums and updating the answer array in place, space can be reduced to O(1).

Why is prefix sum essential for this problem?

Prefix sums allow constant-time access to cumulative sums before or after each index, preventing repeated O(n) calculations per index.

How do I handle a single-element array?

Both leftSum and rightSum are zero, so the absolute difference is 0.

What patterns does this problem follow in arrays?

This follows the array plus prefix sum pattern, where maintaining cumulative sums simplifies computation of differences across elements.

terminal

Solution

Solution 1: Prefix Sum

We define a variable $l$ to represent the sum of elements to the left of index $i$ in the array $\textit{nums}$, and a variable $r$ to represent the sum of elements to the right of index $i$ in the array $\textit{nums}$. Initially, $l = 0$, $r = \sum_{i = 0}^{n - 1} \textit{nums}[i]$.

1

2

3

4

5

6

7

8

9

class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        l, r = 0, sum(nums)
        ans = []
        for x in nums:
            r -= x
            ans.append(abs(l - r))
            l += x
        return ans

Continue Practicing

#2587 rearrange array to maximize prefix score #2588 count the number of beautiful subarrays #2559 count vowel strings in ranges