Left and Right Sum Differences — Editorial

Opening the reading…

Intuitioneach index separates the array into two independent sides

At index i, the value itself belongs to neither sum. The left sum contains nums[0] through nums[i - 1], while the right sum contains nums[i + 1] through nums[n - 1]. Once those two totals are known, the required answer is simply their absolute difference. The first and last positions naturally have an empty side, whose sum is zero.

Adjacent indices share almost all of their elements, so recomputing both sides from scratch wastes that overlap. A forward pass can carry the sum of elements already passed, and a backward pass can carry the sum of elements still to come. Storing those results lets a final pass apply the same absolute-difference rule at every position without repeating any additions.

Approach

Read n and create leftSum and rightSum with n zeroes, because index 0 has no elements on its left and index n - 1 has no elements on its right.

Traverse from index 1 to n - 1 and set leftSum[i] to leftSum[i - 1] + nums[i - 1], because the left side of i is the previous left side plus the element immediately before i.

Traverse from index n - 2 down to 0 and set rightSum[i] to rightSum[i + 1] + nums[i + 1], because the right side of i is the next right side plus the element immediately after i.

Create the answer array with n positions, because one result is required for every original index and the output must not overwrite either directional sum before it is used.

For every index i, store abs(leftSum[i] - rightSum[i]) in answer[i], because the definition asks for the absolute difference and not a signed comparison.

Return answer after all indices have been processed, because each result depends on both directional sums being complete.

Complexitythe bounds count working arrays, not the required result

MEASURE	BOUND	WHY
Time	O(n)	The three loops each visit every index at most once. Their work is sequential rather than nested, so the total number of additions and comparisons is a constant multiple of n.
Space	O(n) extra	The leftSum, rightSum, and answer arrays each hold at most n values. The returned answer is required output and is excluded from the extra-space count; the working arrays still use O(n), which is also the worst case when the input has n elements.

Here n is the length of nums.

Annotated solutionC++ · two directional arrays · explicit prefix and suffix sums

CPPBuild left and right sums in separate passes, then compare them at each index.

#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> leftRightDifference(vector<int>& nums) {
        int n = nums.size();
        vector<int> leftSum(n, 0), rightSum(n, 0);

        for (int i = 1; i < n; ++i) {
            leftSum[i] = leftSum[i - 1] + nums[i - 1];
        }

        for (int i = n - 2; i >= 0; --i) {
            rightSum[i] = rightSum[i + 1] + nums[i + 1];
        }

        vector<int> answer(n);
        for (int i = 0; i < n; ++i) {
            answer[i] = abs(leftSum[i] - rightSum[i]);
        }

        return answer;
    }
};

The offsets in both passes are the key detail. leftSum[i] starts from leftSum[i - 1] and adds nums[i - 1], so nums[i] is excluded. The backward pass mirrors that rule: rightSum[i] starts from rightSum[i + 1] and adds nums[i + 1]. Those exclusions are exactly what make the current element belong to neither side.

The one-pass alternativeless storage, with the total sum carried instead of a suffix array

You can avoid both sum arrays by computing the total sum first. At index i, subtracting nums[i] from the remaining total leaves the sum on the right; the variable left then holds the sum on the left. Compute the answer from those two values, and only afterward add nums[i] to left. This is an optimization in space, not a different result or a faster asymptotic algorithm.

CPPUse the total and a running left sum to derive each right sum without storing suffix values.

#include <cstdlib>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> leftRightDifference(vector<int>& nums) {
        int total = 0;
        for (int value : nums) {
            total += value;
        }

        vector<int> answer(nums.size());
        int left = 0;

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            int right = total - left - nums[i];
            answer[i] = abs(left - right);
            left += nums[i];
        }

        return answer;
    }
};