Left and Right Sum Differences

Easy
271.

Left and Right Sum Differences

EasyArrayPrefix SumAmazonMicrosoft

Left and Right Sum Differences is an easy coding problem on arrays and prefix sum, asked in Amazon and Microsoft interviews.

Given a 0-indexed integer array nums, define leftSum[i] as the sum of the elements strictly to the left of index i and rightSum[i] as the sum of those strictly to the right (both are 0 at the ends).

Return the array answer where answer[i] = abs(leftSum[i] - rightSum[i]).

Example 1

Input
nums = [10,4,8,3]
Output
[15,1,11,22]

Example 2

Input
nums = [1]
Output
[0]

Example 3

Input
nums = [1,2,3]
Output
[5,2,3]

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var leftRightDifference = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Left and Right Sum Differences — Problem & Solution

Left and Right Sum Differences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Left and Right Sum Differences is an easy coding problem on arrays and prefix sum, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Arrays, Prefix Sum
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a 0-indexed integer array nums, define leftSum[i] as the sum of the elements strictly to the left of index i and rightSum[i] as the sum of those strictly to the right (both are 0 at the ends).

Return the array answer where answer[i] = abs(leftSum[i] - rightSum[i]).

Example 1

Input: nums = [10,4,8,3]
Output: [15,1,11,22]

Example 2

Input: nums = [1]
Output: [0]

Example 3

Input: nums = [1,2,3]
Output: [5,2,3]

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 1000

Hints for Left and Right Sum Differences

  1. Hint 1

    One pass gives the total; a second maintains the running left sum.

  2. Hint 2

    The right sum is then total - left - nums[i], with no second array needed.

How to solve Left and Right Sum Differences

One total plus a running left sum gives the right sum as total - left - nums[i].

Approach

  1. Compute total.
  2. Walk with left = 0; write |left - (total - left - x)|; then add x to left.

Why it works

Every element is in exactly one of left, current, or right, so the identity is exact and no second prefix array is needed.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Update left after computing the answer for the current index.

Reference solution

Python

def leftRightDifference(nums):
    total = sum(nums)
    out = []
    left = 0
    for x in nums:
        right = total - left - x
        out.append(abs(left - right))
        left += x
    return out

Java

public static int[] leftRightDifference(int[] nums) {
    int total = 0;
    for (int v : nums) total += v;
    int[] out = new int[nums.length];
    int left = 0;
    for (int i = 0; i < nums.length; i++) {
        int right = total - left - nums[i];
        out[i] = Math.abs(left - right);
        left += nums[i];
    }
    return out;
}

C++

vector<int> leftRightDifference(vector<int>& nums) {
    int total = 0;
    for (int v : nums) total += v;
    vector<int> out;
    int left = 0;
    for (int v : nums) {
        int right = total - left - v;
        out.push_back(abs(left - right));
        left += v;
    }
    return out;
}

JavaScript

var leftRightDifference = function(nums) {
    let total = 0;
    for (let i = 0; i < nums.length; i++) total += nums[i];
    const out = [];
    let left = 0;
    for (let i = 0; i < nums.length; i++) {
        const right = total - left - nums[i];
        out.push(Math.abs(left - right));
        left += nums[i];
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum