Skip to main content
Talentd

Left and Right Sum Differences - Solution & Explanation

EasyArrayPrefix Sum18 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

Given a 0-indexed integer array nums, find a 0-indexed integer array answer where:

  • answer.length == nums.length.
  • answer[i] = |leftSum[i] - rightSum[i]|.

Where:

  • leftSum[i] is the sum of elements to the left of the index i in the array nums. If there is no such element, leftSum[i] = 0.
  • rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0.

Return the array answer.

 

Example 1:

Input: nums = [10,4,8,3]
Output: [15,1,11,22]
Explanation: The array leftSum is [0,10,14,22] and the array rightSum is [15,11,3,0].
The array answer is [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22].

Example 2:

Input: nums = [1]
Output: [0]
Explanation: The array leftSum is [0] and the array rightSum is [0].
The array answer is [|0 - 0|] = [0].

 

Constraints:

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

Approach Overview

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.

Approach 1: Brute Force Calculation

This approach involves calculating the left and right sums independently for each index, resulting in an O(n^2) time complexity. Though this is not the most efficient method, it helps understand the problem.

The code above calculates the left and right sums for each index in a brute force manner. It uses two nested loops to sum the elements to the left and right of each current index.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1) (excluding the space required for the output array 'answer')

Try this approach in the editor →

Approach 2: Optimized Prefix Sum Calculation

This approach reduces the time complexity by using prefix sums. We precompute the total sum of the array and use it to efficiently find the left and right sums for each index.

This solution computes the total sum of the array first. Then, for each index, it uses the total sum and the left sum (tracked dynamically) to calculate right sums more efficiently.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1) (if we don't count the space for the answer array)

Try this approach in the editor →

Approach 3: Prefix Sum

We define a variable l to represent the sum of elements to the left of index i in the array nums, and a variable r to represent the sum of elements to the right of index i in the array nums. Initially, l = 0, r = sum_{i = 0}^{n - 1} nums[i].

We traverse the array nums. For the current number x, we update r = r - x. At this point, l and r represent the sum of elements to the left and right of index i in the array nums, respectively. We add the absolute difference of l and r to the answer array ans, then update l = l + x.

After the traversal, we return the answer array ans.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1), not counting the space for the return value.

Similar problems:

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Calculation

Time Complexity: O(n^2)
Space Complexity: O(1) (excluding the space required for the output array 'answer')

Optimized Prefix Sum Calculation

Time Complexity: O(n)
Space Complexity: O(1) (if we don't count the space for the answer array)

Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force CalculationO(n²)O(1)Useful for understanding the problem or verifying correctness on small arrays.
Optimized Prefix Sum CalculationO(n)O(1)Best general solution for interviews and large inputs.

Video Solution

2574. Left and Right Sum Differences - JAVA - Weekly Contest 334 (Detailed explanation + coding) • Sourin Majumdar • 5,076 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Left and Right Sum Differences easy or hard?
Left and Right Sum Differences is classified as an Easy problem. It mainly tests understanding of array traversal and prefix sum logic. Once the relationship between total sum, left sum, and right sum is recognized, the optimal O(n) solution becomes straightforward.
Left and Right Sum Differences Python/Java solution
In Python or Java, the typical implementation computes the total sum first, then iterates once through the array while maintaining a running left sum. For each index, compute rightSum using the remaining total and append the absolute difference to the result array. The algorithm runs in O(n) time.
How to solve Left and Right Sum Differences in O(n)?
Start by computing the total sum of the array. Initialize leftSum = 0. Iterate through the array, subtract the current value from the total to obtain rightSum, compute abs(leftSum - rightSum), then update leftSum by adding the current value. This keeps all calculations constant time per index and completes in O(n).
What is the best approach for Left and Right Sum Differences?
The optimal approach uses a prefix sum technique. First compute the total sum of the array, then iterate once while maintaining a running left sum. The right sum can be derived by subtracting the current element from the remaining total. This produces each difference in O(1) time per index, resulting in overall O(n) time and O(1) extra space.
Is Left and Right Sum Differences asked at Google/Amazon/Meta?
Array prefix sum problems appear frequently in interviews at companies such as Amazon, Google, and Meta because they test efficient array traversal and cumulative sum techniques. While this exact problem may vary in wording, the prefix sum pattern is a common interview topic.
What data structure is used in Left and Right Sum Differences?
The problem mainly uses a basic array and arithmetic with prefix sums. No advanced data structures are required. The optimized solution maintains two running values—leftSum and remaining rightSum—while iterating through the array.
What is the time complexity of Left and Right Sum Differences?
The brute force solution runs in O(n^2) time because each index recomputes left and right sums by scanning the array. The optimized prefix sum solution runs in O(n) time with a single traversal after calculating the total sum. Both approaches use O(1) auxiliary space aside from the output array.

Ready to solve this problem?

Practice Left and Right Sum Differences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Pivot Index

Next

Find the Distinct Difference Array