2574. Left and Right Sum Differences

Array
Prefix Sum

TIME

O(n)

SPACE

O(1)

Intuition

For each index, the left sum can be tracked while scanning from left to right.

If we know the total sum of the array, then the right sum at index i is:

total - leftSum - nums[i]

So we do not need to build separate leftSum and rightSum arrays.

Approach

Compute the total sum of nums.
Initialize leftSum = 0.
For each index i:
- compute rightSum = total - leftSum - nums[i]
- append abs(leftSum - rightSum) to the answer
- add nums[i] to leftSum
Return the answer.

Complexity

Time: O(n), scan the array once after computing the total
Space: O(1) extra, excluding the returned answer

Edge Cases

Single element -> both side sums are 0
First index -> left sum is 0
Last index -> right sum is 0
Large values -> sums fit within normal integer ranges for the constraints

Code

from typing import List


class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        """
        2574. Left and Right Sum Differences
        Time: O(n)
        Space: O(1)
        """
        total = sum(nums)
        left_sum = 0
        answer = []

        for num in nums:
            right_sum = total - left_sum - num
            answer.append(abs(left_sum - right_sum))
            left_sum += num

        return answer

/**
 * 2574. Left and Right Sum Differences
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int[] leftRightDifference(int[] nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }

        int leftSum = 0;
        int[] answer = new int[nums.length];

        for (int index = 0; index < nums.length; index++) {
            int rightSum = total - leftSum - nums[index];
            answer[index] = Math.abs(leftSum - rightSum);
            leftSum += nums[index];
        }

        return answer;
    }
}