Left and Right Sum Differences - Solution & Explanation

Problem Overview: Given an integer array nums, compute a new array where each index contains the absolute difference between the sum of elements to its left and the sum of elements to its right. For index i, calculate |leftSum - rightSum|. The first element has no left values and the last element has no right values.

Approach 1: Brute Force Calculation (Time: O(n²), Space: O(1))

For each index i, iterate through the array twice: once to sum all elements before i and once to sum all elements after i. Compute abs(leftSum - rightSum) and store the result. This approach directly follows the problem definition and requires no additional data structures. However, because every index performs two scans of the array, the total work becomes quadratic.

This method works for small inputs or when you want a straightforward baseline implementation. It also helps verify correctness before optimizing.

Approach 2: Optimized Prefix Sum Calculation (Time: O(n), Space: O(1))

The key observation: once you know the total sum of the array, you can compute the right sum without scanning again. Start by calculating the total sum. Then iterate through the array while maintaining a running leftSum. For index i, subtract nums[i] from the remaining total to get rightSum. Now compute abs(leftSum - rightSum). After that, update leftSum += nums[i].

This technique uses the idea behind prefix sums: cumulative sums allow constant‑time range calculations. Only one pass through the array is required after computing the total sum, giving linear performance.

Recommended for interviews: The prefix sum approach is the expected solution. It reduces the complexity from O(n²) to O(n) while using constant extra space. Mentioning the brute force approach first shows you understand the raw problem definition, but implementing the optimized prefix-sum pass demonstrates algorithmic awareness and efficient array processing.