2574. Left and Right Sum Differences

Time: O(n)

Space: O(1)

Intuition

For each index i, we need the absolute difference between the sum of elements to the left and the sum of elements to the right. A naive solution recomputes both sums at every index in O(n^2). The key observation is that as we move one step right, only one element crosses from the right side to the left side, so both sums can be updated in O(1) per index.

Algorithm

1Initialize leftSum = 0 and rightSum = sum of all elements.
2For each index i from 0 to n-1:
3 Subtract nums[i] from rightSum so rightSum now represents the sum strictly to the right of i.
4 Set answer[i] = |leftSum - rightSum|.
5 Add nums[i] to leftSum so leftSum represents the sum of elements up to and including i for the next step.
6Return the answer array.

Example Walkthrough

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

1.Start: leftSum = 0, rightSum = 25.
2.i = 0: rightSum = 15, ans[0] = |0 - 15| = 15, leftSum = 10.
3.i = 1: rightSum = 11, ans[1] = |10 - 11| = 1, leftSum = 14.
4.i = 2: rightSum = 3, ans[2] = |14 - 3| = 11, leftSum = 22.
5.i = 3: rightSum = 0, ans[3] = |22 - 0| = 22, leftSum = 25.

Output: [15, 1, 11, 22]

Common Pitfalls

•Subtract nums[i] from rightSum before computing the answer, not after.
•Do not include nums[i] in either leftSum or rightSum when computing answer[i].
•Using prefix and suffix arrays works but uses O(n) extra space; the running-sum method is enough.

2574.cs

// Approach: Single pass with running prefix sums. Keep leftSum (elements before i) and rightSum
// (elements after i); at each index subtract nums[i] from rightSum before computing the answer,
// then add nums[i] to leftSum.
// Time: O(n) Space: O(1) excluding the output array

public class Solution
{
    public int[] LeftRightDifference(int[] nums)
    {
        int[] ans = new int[nums.Length];
        int leftSum = 0;
        int rightSum = nums.Sum();

        for (int i = 0; i < nums.Length; ++i)
        {
            rightSum -= nums[i];
            ans[i] = Math.Abs(leftSum - rightSum);
            leftSum += nums[i];
        }

        return ans;
    }
}

Was this solution helpful?