We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Left and Right Sum Differences

Number: 2714

Difficulty: Easy

Paid? No

Companies: Bloomberg

Problem Description

Given a 0-indexed integer array nums, for each index i we need to calculate two sums:

  • leftSum[i]: the sum of all elements to the left of index i (if none, then 0).
  • rightSum[i]: the sum of all elements to the right of index i (if none, then 0). Return an array answer where answer[i] = |leftSum[i] - rightSum[i]|.

Key Insights

  • The left sum at any index can be computed by maintaining a running cumulative sum.
  • The right sum for index i can be derived by subtracting the current element and the left cumulative sum from the total sum of the array.
  • A single pass can be used after computing the total sum, making the solution efficient.
  • The problem leverages prefix sum techniques to avoid extra passes for computing sums.

Space and Time Complexity

Time Complexity: O(n) because we are iterating over the array a constant number of times. Space Complexity: O(n) for the output array (excluding input). Additional space usage is O(1).

Solution

We first calculate the total sum of the array to know the combined value of all elements. Then, as we iterate through the array, we maintain a cumulative left sum. For each index, we compute the right sum as total sum minus left sum minus the current element. The absolute difference between left sum and right sum is then stored in the answer array. This approach ensures that each element is processed once.

Code Solutions

# Function to calculate left and right sum differences
def leftRightDifference(nums):
    # Calculate the total sum of the array
    total_sum = sum(nums)
    left_sum = 0
    answer = []
    
    # Iterate through each index in the array
    for num in nums:
        # Compute right sum by subtracting left_sum and current number from total_sum
        right_sum = total_sum - left_sum - num
        # Append the absolute difference to the answer list
        answer.append(abs(left_sum - right_sum))
        # Update left_sum with the current element for next iteration
        left_sum += num
        
    return answer

# Example usage:
# print(leftRightDifference([10, 4, 8, 3]))  # Output: [15, 1, 11, 22]
← Back to All Questions