Left and Right Sum Differences — LeetCode 2574 Python Solution

The problem

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.

Example

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].

Python solution

class Solution:
    def leftRigthDifference(self, nums: List[int]) -> List[int]:
        left, right = 0, sum(nums)
        ans = []
        for x in nums:
            right -= x
            ans.append(abs(left - right))
            left += x
        return ans

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2574. Left and Right Sum Differences is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems