Intuition

At first glance, calculating the left and right sums for every single index from scratch sounds like it would take way too long (a nested loop). The most intuitive way to speed this up is to "remember" our previous calculations. If we keep a running total from the left side and a running total from the right side, we can solve this problem in just a few quick sweeps through the array!

There is also a brilliant mathematical trick happening in this specific code: instead of strictly finding the exclusive left and right sums (where nums[i] is left out), the code calculates the inclusive left and right sums. Why does this work? Because when you subtract the two sums, the current element nums[i] cancels itself out entirely!
(Left_Sum_Exclusive + nums[i]) - (Right_Sum_Exclusive + nums[i]) = Left_Sum_Exclusive - Right_Sum_Exclusive.

Approach

1. Build the Left Sums: We iterate through the array from left to right, maintaining a curr_sum and appending it to our left_sum array. This gives us the running total up to and including each index.
2. Build the Right Sums: We reset curr_sum to 0 and iterate through the array backwards (right to left), building up our right_sum array.
3. Align the Arrays: Because we built right_sum backwards, we need to reverse it (right_sum[::-1]) so that index i properly lines up with the original nums array.
4. Calculate Differences: Finally, we iterate through the indices from 0 to n-1, taking the absolute difference abs(left_sum[i] - right_sum[i]) and appending it to our answer array.

Complexity

• Time complexity:

$O(n)$

(We pass through the array a few distinct times—once for the left sums, once for the right sums, once to reverse, and once to calculate the differences. Since these loops are not nested, the time scales linearly with the size of the input array).

• Space complexity:

$O(n)$

(We allocate extra memory to store the left_sum, right_sum, and answer arrays, which all scale linearly with the input size).

Code

class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        n = len(nums)

        curr_sum = 0
        left_sum = []
        for i in range(n):
            curr_sum += nums[i]
            left_sum.append(curr_sum)

        curr_sum = 0
        right_sum = []
        for i in range(n-1, -1, -1):
            curr_sum += nums[i]
            right_sum.append(curr_sum)
        right_sum = right_sum[::-1]

        answer = []
        for i in range(n):
            answer.append(abs(left_sum[i] - right_sum[i]))

        return answer

✨ If this explanation helped you understand the prefix sum trick, please drop an UPVOTE! ⬆️💖 It keeps me motivated to create more beginner-friendly solutions for the community! Happy Coding! ✨