Skip to content

Latest commit

 

History

History
81 lines (57 loc) · 3.15 KB

027.md

File metadata and controls

81 lines (57 loc) · 3.15 KB

2574. Left and Right Sum Differences

Difficulty: 🟢 Easy

Given a 0-indexed integer array nums, find a 0-indexed integer array answer where:

  • answer.length == nums.length.
  • answer[i] = |leftSum[i] - rightSum[i]|.

Where:

  • leftSum[i] is the sum of elements to the left of the index i in the array nums. If there is no such element, leftSum[i] = 0.
  • rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0. Return the array answer.

Examples:

Example 1:

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].
The array answer is [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22].

Example 2:

Input: nums = [1]
Output: [0]
Explanation: The array leftSum is [0] and the array rightSum is [0].
The array answer is [|0 - 0|] = [0].

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 105

Solutions

O(n) solution in Python3

class Solution:
    def leftRightDifference(self, nums: List[int]) -> List[int]:
        right, left_sum, answer = 0, sum(nums), []
        for num in nums:
            right += num
            answer.append(abs(right-left_sum))
            left_sum -= num
        return answer

The given solution calculates the array answer by iteratively summing the elements from left to right and calculating the difference between the left and right sums at each index.

The algorithm works as follows:

  1. Initialize the variables right to 0, left_sum to the sum of all elements in nums, and an empty array answer to store the results.
  2. Iterate through each element num in the nums array.
    • Add num to the right sum.
    • Calculate the absolute difference between right and left_sum and append it to the answer array.
    • Subtract num from the left_sum.
  3. Return the answer array, which contains the absolute differences between the left and right sums at each index.

The algorithm calculates the left sum by subtracting the current element from the total sum and adds the current element to the right sum. It then calculates the absolute difference between the left and right sums and appends it to the answer array.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the length of the nums array. The algorithm iterates through each element of nums once and performs constant-time operations.

The space complexity of the algorithm is O(n) as it uses additional space to store the answer array, which has the same length as nums.

Summary

The given solution calculates the array answer by iteratively summing the elements from left to right and calculating the difference between the left and right sums at each index. It has a time complexity of O(n) and a space complexity of O(n), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.