Left and Right Sum Differences

easy prefix sum array suffix sum

Problem

Given a 0-indexed array nums, let leftSum[i] be the sum of all elements to the left of index i and rightSum[i] the sum of all elements to its right (0 when there is no such element). Return an array answer where answer[i] = |leftSum[i] - rightSum[i]|.

Inputnums = [10, 4, 8, 3]

Output[15, 1, 11, 22]

leftSum = [0,10,14,22], rightSum = [15,11,3,0]; answer = [|0-15|, |10-11|, |14-3|, |22-0|].

Inputnums = [1]

Output[0]

A single element has nothing on either side: leftSum = [0], rightSum = [0].

nums (comma-separated)

def left_right_difference(nums):
    n = len(nums)
    answer = [0] * n
    left = 0
    right = sum(nums)
    for i in range(n):
        right -= nums[i]
        answer[i] = abs(left - right)
        left += nums[i]
    return answer

function leftRightDifference(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(0);
  let left = 0;
  let right = nums.reduce((a, b) => a + b, 0);
  for (let i = 0; i < n; i++) {
    right -= nums[i];
    answer[i] = Math.abs(left - right);
    left += nums[i];
  }
  return answer;
}

int[] leftRightDifference(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    int left = 0, right = 0;
    for (int v : nums) right += v;
    for (int i = 0; i < n; i++) {
        right -= nums[i];
        answer[i] = Math.abs(left - right);
        left += nums[i];
    }
    return answer;
}

vector<int> leftRightDifference(vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 0);
    int left = 0, right = 0;
    for (int v : nums) right += v;
    for (int i = 0; i < n; i++) {
        right -= nums[i];
        answer[i] = abs(left - right);
        left += nums[i];
    }
    return answer;
}

Explanation

The naive way is, for every index i, to re-sum everything on its left and everything on its right — that re-walks the array and costs O(n²). We can do it in one pass by carrying the two sums with us.

Keep two running totals: left is the sum of elements already passed (strictly to the left of i), and right is the sum of elements still ahead (strictly to the right of i). Before the loop, nothing is on the left so left = 0, and everything is on the right so right = sum(nums).

At index i we first remove nums[i] from right, because element i itself is not "to the right" of i. Now right holds rightSum[i] and left already holds leftSum[i], so answer[i] = |left - right|.

After recording the answer we fold nums[i] into left, preparing it to be leftSum[i+1] for the next index. Each value moves from the right bucket to the left bucket exactly once.

For nums = [10,4,8,3]: right starts at 25. At i=0, right→15, answer=|0−15|=15, left→10. At i=1, right→11, answer=|10−11|=1, left→14, and so on, giving [15,1,11,22].

Time: O(n) Space: O(n)