Problem Statement in English

You’re given a 0-indexed integer array nums. The left sum of an index i is the sum of elements to the left of i in nums. The right sum of an index i is the sum of elements to the right of i in nums. The left-right difference of an index i is the absolute difference between the left sum and right sum of i.

Return an array answer of size n where answer[i] is the left-right difference for index i.

Approach

To solve this problem, we can use two auxiliary arrays, leftSum and rightSum, to store the cumulative sums from the left and right sides of the input array nums, respectively.

We will iterate through the nums array twice:

  1. In the first pass, we will fill the leftSum array such that leftSum[i] contains the sum of all elements to the left of index i.
  2. In the second pass, we will fill the rightSum array such that rightSum[i] contains the sum of all elements to the right of index i.

Finally, we will iterate through the nums array once more to calculate the left-right difference for each index i by taking the absolute difference between leftSum[i] and rightSum[i], and store the result in the answer array.

And we’re done!

Solution in Python


class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        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 reversed(range(n - 1)):
            rightSum[i] = rightSum[i + 1] + nums[i + 1]

        return [abs(leftSum[i] - rightSum[i]) for i in range(n)]

Complexity

  • Time: $O(n)$
    Since we have to iterate through the nums array three times, the time complexity is linear with respect to the size of the input array.

  • Space: $O(n)$
    Since we are using two additional arrays leftSum and rightSum of size n, the space complexity is also linear with respect to the size of the input array.

And we are done.