We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Left and Right Sum Differences

Difficulty: Easy

Problem Description

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 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 an integer array answer of size n where answer[i] = |leftSum[i] - rightSum[i]|.

Key Insights

The problem requires calculating the sums of elements to the left and right of each index in a single pass.
We can utilize prefix sums to efficiently compute the left and right sums.
The absolute difference of the left and right sums for each index will yield the required result.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will:

Create two arrays, leftSum and rightSum, both initialized to zero.
Iterate through the nums array to populate the leftSum array by accumulating the sum of elements to the left.
Iterate through the nums array in reverse to populate the rightSum array by accumulating the sum of elements to the right.
Finally, compute the absolute difference between the corresponding elements of leftSum and rightSum to form the answer array.

The algorithm primarily uses two arrays to store the sums, making it efficient in terms of both time and space.

Code Solutions

def left_right_sum_difference(nums):
    n = len(nums)
    leftSum = [0] * n
    rightSum = [0] * n
    
    for i in range(1, n):
        leftSum[i] = leftSum[i - 1] + nums[i - 1]
    
    for i in range(n - 2, -1, -1):
        rightSum[i] = rightSum[i + 1] + nums[i + 1]
    
    answer = [abs(leftSum[i] - rightSum[i]) for i in range(n)]
    return answer

← Back to All Questions