Defuse the Bomb

TIP103 Unit 1 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays

U-nderstand

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

• Q: What is the input to the function?

  • A: The input consists of a circular array code of integers and an integer k representing the decryption key.

• Q: What is the expected output of the function?

  • A: The function should return a new array where each element is replaced according to the rules defined by k.

• Q: How is the replacement done?

  • A:
    • If k > 0, each element at index i is replaced by the sum of the next k elements.
    • If k < 0, each element at index i is replaced by the sum of the previous -k elements.
    • If k == 0, each element is replaced by 0.

• Q: How does the circular nature of the array affect the replacement?

  • A: The array is treated as circular, meaning the element after the last one is the first one, and the element before the first one is the last one.

• Q: What should the function return if k == 0?

  • A: If k == 0, the function should return an array of zeros of the same length as code.

• The function defuse() should take a circular array code and an integer k, returning a new array where each element is replaced based on the value of k.

HAPPY CASE
Input: code = [5, 7, 1, 4], k = 3
Expected Output: [12, 10, 16, 13]

Input: code = [2, 4, 9, 3], k = -2
Expected Output: [12, 5, 6, 13]

EDGE CASE
Input: code = [1, 2, 3, 4], k = 0
Expected Output: [0, 0, 0, 0]

Input: code = [5], k = 1
Expected Output: [5]

M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For circular array problems, some things we want to consider are:

• Modulo indexing: index (i + j) % n wraps forward past the last element, and (i - j) % n wraps backward past the first element. Python’s % returns a result with the same sign as the divisor, so (0 - 1) % 4 is 3, not -1.
• Building the answer in a separate result list, because every element is replaced at the same time and each sum must use the original values, not ones that were already replaced.
• Prefix sums or a sliding window, which can find every window sum in linear time instead of re-adding |k| elements for each index (see E-valuate).

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Depending on the value of k, either sum the next k elements or the previous k elements for each element in the array. Use modulo arithmetic to handle the circular nature of the array.

1. Initialize `result` as a list of zeros with the same length as `code`.
2. If `k == 0`, return `result`.
3. Iterate through each element in `code`:
   - Initialize `sum_val` to 0.
   - If `k > 0`, sum the next `k` elements:
     - For `j` from 1 to `k`, add `code[(i + j) % n]` to `sum_val`.
   - If `k < 0`, sum the previous `-k` elements:
     - For `j` from 1 to `-k`, add `code[(i - j) % n]` to `sum_val`.
   - Set `result[i]` to `sum_val`.
4. Return `result`

⚠️ Common Mistakes

• Not handling the circular nature of the array correctly.
• Off-by-one errors in indexing elements for summation.

I-mplement

Implement the code to solve the algorithm.

def defuse(code, k):
    n = len(code)
    result = [0] * n
    
    if k == 0:
        return result
    
    for i in range(n):
        sum_val = 0
        if k > 0:
            for j in range(1, k + 1):
                sum_val += code[(i + j) % n]
        else:
            for j in range(1, -k + 1):
                sum_val += code[(i - j) % n]
        
        result[i] = sum_val
    
    return result

R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

Trace code = [2, 4, 9, 3], k = -2 (n = 4), which sums the previous 2 elements:

• i = 0: code[(0 - 1) % 4] = code[3] = 3, code[(0 - 2) % 4] = code[2] = 9, so result[0] = 12
• i = 1: code[0] = 2, code[3] = 3, so result[1] = 5
• i = 2: code[1] = 4, code[0] = 2, so result[2] = 6
• i = 3: code[2] = 9, code[1] = 4, so result[3] = 13

print(defuse([5, 7, 1, 4], 3))   # Output: [12, 10, 16, 13]
print(defuse([2, 4, 9, 3], -2))  # Output: [12, 5, 6, 13]
print(defuse([1, 2, 3, 4], 0))   # Output: [0, 0, 0, 0]
print(defuse([5], 1))            # Output: [5]

In the last edge case the “next” element wraps back around to the element itself, because (0 + 1) % 1 is 0. The canonical LeetCode problem limits k to the range -(n - 1) to n - 1, so for a one-element list it only allows k = 0. This case shows what the code does outside that range.

E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the length of code.

• Time Complexity: O(N * |k|), because the inner loop adds |k| elements for each of the N indices. Since |k| is at most N - 1, the worst case is O(N^2).
• Space Complexity: O(N) for the result list that is returned. Apart from that output, the function uses only O(1) extra space (n, sum_val, and the loop counters).

Follow-up: A prefix-sum version runs in O(N) time. Build prefix sums over code + code, so that every circular window becomes one contiguous range, and compute each window sum as the difference of two prefix values. This trades O(N) extra space for not re-adding |k| elements at every index.