# 2574. Left and Right Sum Differences

## Approach 1: Prefix/Suffix array

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: vector leftRigthDifference(vector& nums) { const int n = nums.size(); vector ans(n); vector leftSum(n); vector rightSum(n); int prefix = 0; int suffix = 0; for (int i = 0; i < n; ++i) { if (i > 0) prefix += nums[i - 1]; leftSum[i] = prefix; } for (int i = n - 1; i >= 0; --i) { if (i + 1 < n) suffix += nums[i + 1]; rightSum[i] = suffix; } for (int i = 0; i < n; ++i) ans[i] = abs(leftSum[i] - rightSum[i]); return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public int[] leftRigthDifference(int[] nums) { final int n = nums.length; int[] ans = new int[n]; int[] leftSum = new int[n]; int[] rightSum = new int[n]; int prefix = 0; int suffix = 0; for (int i = 0; i < n; ++i) { if (i > 0) prefix += nums[i - 1]; leftSum[i] = prefix; } for (int i = n - 1; i >= 0; --i) { if (i + 1 < n) suffix += nums[i + 1]; rightSum[i] = suffix; } for (int i = 0; i < n; ++i) ans[i] = Math.abs(leftSum[i] - rightSum[i]); return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def leftRigthDifference(self, nums: List[int]) -> List[int]: n = len(nums) leftSum = [0] * n rightSum = [0] * n prefix = 0 suffix = 0 for i in range(n): if i > 0: prefix += nums[i - 1] leftSum[i] = prefix for i in range(n - 1, -1, -1): if i + 1 < n: suffix += nums[i + 1] rightSum[i] = suffix return [abs(l - r) for l, r in zip(leftSum, rightSum)] 

## Approach 2: $O(1)$ extra space

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: vector leftRigthDifference(vector& nums) { vector ans; int leftSum = 0; int rightSum = accumulate(begin(nums), end(nums), 0); for (const int num : nums) { rightSum -= num; ans.push_back(abs(leftSum - rightSum)); leftSum += num; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int[] leftRigthDifference(int[] nums) { int[] ans = new int[nums.length]; int leftSum = 0; int rightSum = Arrays.stream(nums).sum(); for (int i = 0; i < nums.length; ++i) { rightSum -= nums[i]; ans[i] = Math.abs(leftSum - rightSum); leftSum += nums[i]; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def leftRigthDifference(self, nums: List[int]) -> List[int]: ans = [] leftSum = 0 rightSum = sum(nums) for num in nums: rightSum -= num ans.append(abs(leftSum - rightSum)) leftSum += num return ans