Left and Right Sum Differences - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 2 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Prefix Sums, Iteration

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• The function left_right_difference() should take an integer array nums and return an integer array answer where each element is the difference between the sum of elements to its left and the sum of elements to its right.

HAPPY CASE
Input: [10, 4, 8, 3]
Expected Output: [-15, -1, 11, 22]

Input: [1, 2, 3, 4, 5]
Expected Output: [-14, -11, -6, 1, 10]

EDGE CASE
Input: [1]
Expected Output: [0]

Input: [0, 0, 0, 0]
Expected Output: [0, 0, 0, 0]

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Calculate the prefix sums for the left and right sides of each index and then compute the differences.

1. Initialize arrays `left_sum` and `right_sum` with zeros, both of length `n` (length of `nums`).
2. Initialize an array `answer` with zeros, also of length `n`.
3. Calculate `left_sum`:
   a. Iterate from index 1 to n-1.
   b. For each index, `left_sum[i] = left_sum[i - 1] + nums[i - 1]`.
4. Calculate `right_sum`:
   a. Iterate from index n-2 to 0.
   b. For each index, `right_sum[i] = right_sum[i + 1] + nums[i + 1]`.
5. Calculate `answer`:
   a. Iterate from index 0 to n-1.
   b. For each index, `answer[i] = left_sum[i] - right_sum[i]`.
6. Return `answer`.

⚠️ Common Mistakes

• Incorrectly indexing when calculating left_sum and right_sum.
• Forgetting to initialize the left_sum and right_sum arrays.

I-mplement

Implement the code to solve the algorithm.

def left_right_difference(nums):
    n = len(nums)
    left_sum = [0] * n
    right_sum = [0] * n
    answer = [0] * n
    
    # Calculate left_sum
    for i in range(1, n):
        left_sum[i] = left_sum[i - 1] + nums[i - 1]
    
    # Calculate right_sum
    for i in range(n - 2, -1, -1):
        right_sum[i] = right_sum[i + 1] + nums[i + 1]
    
    # Calculate answer
    for i in range(n):
        answer[i] = left_sum[i] - right_sum[i]
    
    return answer