Left and Right Sum Differences solution and explanation
Google
9 more videos on this problem
2574. Left and Right Sum Differences - JAVA - Weekly Contest 334 (Detailed explanation + coding)Sourin Majumdar · 6:49 · 5K views
Left and RIght sum differences (LeetCode 2574) | Constant space solutionNikhil Lohia · 14:25 · 2K views
Left and Right Sum Differences - leetcode 2574Leetcoding · 7:36 · 1K views
Leetcode Weekly Contest 334 | 2574 : Left And Right Sum Differences Solution | In Hindi EditorialCoding Community | Newton School · 7:52 · 1K views
2574. Left and Right Sum Differences (Leetcode Easy)Programming Live with Larry · 2:07 · 820 views
Leetcode 2574 || Left and Right Sum Differences. || Leetcode Weekly Easy || cppKomal Pal · 6:09 · 453 views
LeetCode 2574 : Left and Right Sum Differences || EASY || JAVA || Detailed SolutionCodeGPT · 9:13 · 437 views
Leetcode Problem 2574. Left and Right Sum Differences.Leetcode Solution 2574.Competitive programmingCodingForBeginners · 12:15 · 376 views
leetcode 2574. Left and Right Sum Differences - partial sumCode-Yao · 7:50 · 286 views
2574. Left and Right Sum Differences | Leetcode Daily - PythonLeetcode Daily · 5:55 · 222 views
The problem
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 indexiin the arraynums. If there is no such element,leftSum[i] = 0.rightSum[i]is the sum of elements to the right of the indexiin the arraynums. 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 <= 10001 <= 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.
def calculate_sums(nums):
n = len(nums)
answer = []
for i in range(n):
left_sum = sum(nums[:i])
right_sum = sum(nums[i+1:])
answer.append(abs(left_sum - right_sum))
return answer
nums = [10, 4, 8, 3]
answer = calculate_sums(nums)
print(answer)import java.util.Arrays;
public class LeftRightSum {
public static int[] calculateSums(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
for (int i = 0; i < n; i++) {
int leftSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
int rightSum = 0;
for (int j = i + 1; j < n; j++) {
rightSum += nums[j];
}
answer[i] = Math.abs(leftSum - rightSum);
}
return answer;
}
public static void main(String[] args) {
int[] nums = {10, 4, 8, 3};
int[] answer = calculateSums(nums);
System.out.println(Arrays.toString(answer));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> calculateSums(vector<int>& nums) {
int n = nums.size();
vector<int> answer(n);
for (int i = 0; i < n; ++i) {
int leftSum = 0;
for (int j = 0; j < i; ++j) {
leftSum += nums[j];
}
int rightSum = 0;
for (int j = i + 1; j < n; ++j) {
rightSum += nums[j];
}
answer[i] = abs(leftSum - rightSum);
}
return answer;
}
int main() {
vector<int> nums = {10, 4, 8, 3};
vector<int> answer = calculateSums(nums);
for(int& val : answer) {
cout << val << " ";
}
return 0;
}function calculateSums(nums) {
let n = nums.length;
let answer = [];
for (let i = 0; i < n; i++) {
let leftSum = 0;
for (let j = 0; j < i; j++) {
leftSum += nums[j];
}
let rightSum = 0;
for (let j = i + 1; j < n; j++) {
rightSum += nums[j];
}
answer.push(Math.abs(leftSum - rightSum));
}
return answer;
}
let nums = [10, 4, 8, 3];
let answer = calculateSums(nums);
console.log(answer);#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void calculateSums(int* nums, int numsSize, int* answer) {
for (int i = 0; i < numsSize; i++) {
int leftSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
int rightSum = 0;
for (int j = i + 1; j < numsSize; j++) {
rightSum += nums[j];
}
answer[i] = abs(leftSum - rightSum);
}
}
int main() {
int nums[] = {10, 4, 8, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int* answer = (int*)malloc(numsSize * sizeof(int));
calculateSums(nums, numsSize, answer);
for (int i = 0; i < numsSize; i++) {
printf("%d ", answer[i]);
}
free(answer);
return 0;
}using System;
public class LeftRightSum {
public static int[] CalculateSums(int[] nums) {
int n = nums.Length;
int[] answer = new int[n];
for (int i = 0; i < n; i++) {
int leftSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
int rightSum = 0;
for (int j = i + 1; j < n; j++) {
rightSum += nums[j];
}
answer[i] = Math.Abs(leftSum - rightSum);
}
return answer;
}
public static void Main() {
int[] nums = {10, 4, 8, 3};
int[] answer = CalculateSums(nums);
Console.WriteLine(string.Join(" ", answer));
}
}This Python solution calculates the left and right sums for each index using slicing and the sum function, then appends the result to the answer list.
Time Complexity: O(n^2)
Space Complexity: O(1) (excluding the space required for the output array 'answer')
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.
def calculate_sums(nums):
total_sum = sum(nums)
left_sum = 0
answer = []
for num in nums:
right_sum = total_sum - left_sum - num
answer.append(abs(left_sum - right_sum))
left_sum += num
return answer
nums = [10, 4, 8, 3]
answer = calculate_sums(nums)
print(answer)import java.util.Arrays;
public class LeftRightSum {
public static int[] calculateSums(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
int totalSum = Arrays.stream(nums).sum();
int leftSum = 0;
for (int i = 0; i < n; i++) {
int rightSum = totalSum - leftSum - nums[i];
answer[i] = Math.abs(leftSum - rightSum);
leftSum += nums[i];
}
return answer;
}
public static void main(String[] args) {
int[] nums = {10, 4, 8, 3};
int[] answer = calculateSums(nums);
System.out.println(Arrays.toString(answer));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> calculateSums(vector<int>& nums) {
int n = nums.size();
vector<int> answer(n);
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
int leftSum = 0;
for (int i = 0; i < n; ++i) {
int rightSum = totalSum - leftSum - nums[i];
answer[i] = abs(leftSum - rightSum);
leftSum += nums[i];
}
return answer;
}
int main() {
vector<int> nums = {10, 4, 8, 3};
vector<int> answer = calculateSums(nums);
for(int val : answer) {
cout << val << " ";
}
return 0;
}function calculateSums(nums) {
let totalSum = nums.reduce((acc, num) => acc + num, 0);
let leftSum = 0;
let answer = [];
for (let num of nums) {
let rightSum = totalSum - leftSum - num;
answer.push(Math.abs(leftSum - rightSum));
leftSum += num;
}
return answer;
}
let nums = [10, 4, 8, 3];
let answer = calculateSums(nums);
console.log(answer);#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void calculateSums(int* nums, int numsSize, int* answer) {
int totalSum = 0;
for (int i = 0; i < numsSize; i++) {
totalSum += nums[i];
}
int leftSum = 0;
for (int i = 0; i < numsSize; i++) {
int rightSum = totalSum - leftSum - nums[i];
answer[i] = abs(leftSum - rightSum);
leftSum += nums[i];
}
}
int main() {
int nums[] = {10, 4, 8, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int* answer = (int*)malloc(numsSize * sizeof(int));
calculateSums(nums, numsSize, answer);
for (int i = 0; i < numsSize; i++) {
printf("%d ", answer[i]);
}
free(answer);
return 0;
}using System;
using System.Linq;
public class LeftRightSum {
public static int[] CalculateSums(int[] nums) {
int n = nums.Length;
int[] answer = new int[n];
int totalSum = nums.Sum();
int leftSum = 0;
for (int i = 0; i < n; i++) {
int rightSum = totalSum - leftSum - nums[i];
answer[i] = Math.Abs(leftSum - rightSum);
leftSum += nums[i];
}
return answer;
}
public static void Main() {
int[] nums = {10, 4, 8, 3};
int[] answer = CalculateSums(nums);
Console.WriteLine(string.Join(" ", answer));
}
}This Python solution calculates the total sum initially and adjusts the left and right sums in a single loop, using a prefix sum approach which is efficient and concise.
Time Complexity: O(n)
Space Complexity: O(1) (if we don't count the space for the answer array)
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:
function leftRightDifference(nums: number[]): number[] {
let [l, r] = [0, nums.reduce((a, b) => a + b, 0)];
const ans: number[] = [];
for (const x of nums) {
r -= x;
ans.push(Math.abs(l - r));
l += x;
}
return ans;
}func leftRightDifference(nums []int) []int {
l, r := 0, 0
for _, x := range nums {
r += x
}
n := len(nums)
ans := make([]int, n)
for i, x := range nums {
r -= x
ans[i] = abs(l - r)
l += x
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn left_right_difference(nums: Vec<i32>) -> Vec<i32> {
let mut l = 0;
let mut r: i32 = nums.iter().sum();
let mut ans = Vec::with_capacity(nums.len());
for x in nums {
r -= x;
ans.push((l - r).abs());
l += x;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Calculation | Time Complexity: O(n^2) |
| Optimized Prefix Sum Calculation | Time Complexity: O(n) |
| Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Calculation | O(n²) | O(1) | Useful for understanding the problem or verifying correctness on small arrays. |
| Optimized Prefix Sum Calculation | O(n) | O(1) | Best general solution for interviews and large inputs. |
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.