algoadvance

Leetcode 2574. Left and Right Sum Differences

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 index i in the array nums. If there is no such element, leftSum[i] is 0.
• rightSum[i] is the sum of elements to the right of index i in the array nums. If there is no such element, rightSum[i] is 0.

Return the answer array.

Example 1

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

Explanation:
- For index 0, leftSum is [], rightSum is [4,8,3], and |0 - 15| = 15.
- For index 1, leftSum is [10], rightSum is [8,3], and |10 - 11| = 1.
- For index 2, leftSum is [10,4], rightSum is [3], and |14 - 3| = 11.
- For index 3, leftSum is [10,4,8], rightSum is [], and |22 - 0| = 22.

Example 2

Input: nums = [1,2,3,4]
Output: [10,8,6,4]

Explanation:
- For index 0, leftSum is [], rightSum is [2,3,4], and |0 - 9| = 9.
- For index 1, leftSum is [1], rightSum is [3,4], and |1 - 7| = 6.
- For index 2, leftSum is [1,2], rightSum is [4], and |3 - 4| = 1.
- For index 3, leftSum is [1,2,3], rightSum is [], and |6 - 0| = 6.

Clarifying Questions

1. Can the input array be empty?
2. What are the constraints on the elements of the input array?

Strategy

1. Initialize Sum Variables: Use two arrays, one for the cumulative left sums (leftSum) and one for the cumulative right sums (rightSum).
2. Compute Left Sums: Traverse the array from left to right to compute the left sums.
3. Compute Right Sums: Traverse the array from right to left to compute the right sums.
4. Calculate Answer: Use the left and right sums to compute the absolute differences and store them in the answer array.
5. Return Result: Return the answer array.

Code

public class Solution {
    public int[] leftRightDifference(int[] nums) {
        int n = nums.length;
        int[] leftSum = new int[n];
        int[] rightSum = new int[n];
        int[] answer = new int[n];
        
        // Calculate left sums
        for (int i = 1; i < n; i++) {
            leftSum[i] = leftSum[i - 1] + nums[i - 1];
        }
        
        // Calculate right sums
        for (int i = n - 2; i >= 0; i--) {
            rightSum[i] = rightSum[i + 1] + nums[i + 1];
        }
        
        // Calculate answer array
        for (int i = 0; i < n; i++) {
            answer[i] = Math.abs(leftSum[i] - rightSum[i]);
        }
        
        return answer;
    }
}

Time Complexity

• Time Complexity: O(n) where n is the length of the input array nums. This is because we are iterating through the array three times: once for calculating leftSum, once for calculating rightSum, and once for computing the answer.
• Space Complexity: O(n) due to the additional arrays leftSum and rightSum.

This solution efficiently computes the required difference arrays with linear time complexity and minimal extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?