LeetCode Problem 2574
Link of the Problem to try -: Link
You are given a 0-indexed integer array nums of size n.
Define two arrays leftSum and rightSum 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 an integer array answer of size n where answer[i] = |leftSum[i] - rightSum[i]|.
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
Left and Right Sum Difference in an Array (Java) – Easy & Optimal Approaches
This problem can be solved using multiple approaches. In this blog, I will explain two simple and effective ways to solve the Left and Right Sum Difference problem.
- Approach 1: A straightforward and beginner-friendly solution
- Approach 2: A more optimal solution with better space efficiency
Both approaches are easy to understand and suitable for submitting on LeetCode.
Approach 1: Simplest and Easy to Understand
Explanation
In this approach, we use three arrays of size n:
prefix[]to store the sum of elements on the left of each indexsuffix[]to store the sum of elements on the right of each indexans[]to store the final result
Steps
- Build the
prefixarray using a forward loop. - Build the
suffixarray using a backward loop. - Iterate through the array and calculate the absolute difference between prefix and suffix sums.
Time & Space Complexity
- Time Complexity:
O(n) - Space Complexity:
O(n)(extra arrays used)
Java Code
public int[] leftRightDifference(int[] nums) {
int pref[] = new int[nums.length];
int suff[] = new int[nums.length];
int ans[] = new int[nums.length];
pref[0] = 0;
for (int i = 1; i < nums.length; i++) {
pref[i] = pref[i - 1] + nums[i - 1];
}
suff[nums.length - 1] = 0;
for (int i = nums.length - 2; i >= 0; i--) {
suff[i] = suff[i + 1] + nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
ans[i] = Math.abs(pref[i] - suff[i]);
}
return ans;
}
Why Use This Approach?
- Very easy to understand
- Best for beginners
- Clear separation of prefix and suffix logic
Approach 2: Optimal Solution (Best for Interviews)
Explanation
This is the most optimal approach, where we only use one result array.
Instead of creating a suffix array, we:
- Calculate the total sum of the array
- Maintain a running left sum
- Compute the right sum using the formula:
rightSum = totalSum - leftSum - currentElement
This removes the need for extra arrays and reduces space usage.
Time & Space Complexity
- Time Complexity:
O(n) - Space Complexity:
O(1)(excluding output array)
Java Code
public int[] leftRightDifference(int[] nums) {
int ans[] = new int[nums.length];
int total = 0;
int left = 0;
for (int num : nums) {
total += num;
}
for (int i = 0; i < nums.length; i++) {
int right = total - left - nums[i];
ans[i] = Math.abs(left - right);
left += nums[i];
}
return ans;
}
Why This Is Optimal?
- Uses constant extra space
- Clean and efficient logic
- Ideal for coding interviews and competitive programming
