TIP102 Unit 1 Session 2 Standard (Click for link to problem statements)
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?
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]
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
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