Skip to content

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<int> leftRigthDifference(vector<int>& nums) {
    const int n = nums.size();
    vector<int> ans(n);
    vector<int> leftSum(n);
    vector<int> 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<int> leftRigthDifference(vector<int>& nums) {
    vector<int> ans;
    int leftSum = 0;
    int rightSum = accumulate(nums.begin(), nums.end(), 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