Domain 1EasyCORE

Defuse the Bomb

The problem requires us to decrypt a circular array `code` using a key `k`. The decryption process involves replacing each element in the array with either the sum of the next `k` elements (if `k > 0`), the sum of the previous `k` elements (if `k < 0`), or `0` (if `k == 0`). The array is circular, meaning that after the last element, it wraps around to the first element, and vice versa.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

1652. Defuse the Bomb

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 61.7%


Problem Breakdown

The problem requires us to decrypt a circular array code using a key k. The decryption process involves replacing each element in the array with either the sum of the next k elements (if k > 0), the sum of the previous k elements (if k < 0), or 0 (if k == 0). The array is circular, meaning that after the last element, it wraps around to the first element, and vice versa.

Inputs:

  • A circular array code of length n.
  • An integer key k.

Outputs:

  • A new array where each element is replaced according to the rules specified by k.

Implicit Constraints or Edge Cases:

  • The array can be as small as 1 element.
  • k can range from -(n - 1) to n - 1.
  • If k == 0, all elements in the output should be 0.
  • The circular nature of the array must be handled correctly.

Intuition

A brute-force approach would involve iterating over each element and calculating the sum of the next or previous k elements for each position. This would result in a time complexity of O(n * |k|), which is inefficient for larger values of n and |k|.

The key insight to improve this is to use a sliding window technique. By maintaining a running sum of the current window of size |k|, we can update the sum efficiently as we slide the window across the array. This reduces the time complexity to O(n).

Approach

  1. Initialize Variables:

    • Create an output array result of the same length as code.
    • Calculate the absolute value of k and store it in a variable abs_k.
  2. Handle k == 0 Case:

    • If k is 0, fill the entire result array with 0s.
  3. Sliding Window Technique:

    • Initialize a running sum window_sum to 0.
    • Calculate the initial window sum for the first abs_k elements.
    • For each element in the array, update the corresponding position in the result array with the current window_sum.
    • Slide the window by subtracting the element that is leaving the window and adding the new element entering the window.
  4. Return the Result:

    • Return the result array after processing all elements.

Complexity Analysis

  • Time Complexity: O(n)

    • We iterate through the array once to calculate the initial window sum.
    • We then slide the window across the array, updating the running sum in constant time for each element.
  • Space Complexity: O(n)

    • We use an additional array result of the same length as code.

Solution

def decrypt(code: List[int], k: int) -> List[int]:
    n = len(code)
    result = [0] * n
    
    if k == 0:
        return result
    
    abs_k = abs(k)
    window_sum = sum(code[:abs_k])
    
    for i in range(n):
        if k > 0:
            result[i] = window_sum
            window_sum -= code[i]
            window_sum += code[(i + abs_k) % n]
        else:
            result[i] = window_sum
            window_sum -= code[(i - abs_k) % n]
            window_sum += code[i]
    
    return result

Edge Cases Handled

  • k == 0: The output array is filled with 0s.
  • k > 0: The sum of the next k elements is calculated correctly for each position, wrapping around at the end.
  • k < 0: The sum of the previous k elements is calculated correctly for each position, wrapping around at the beginning.
  • Single Element Array: The function handles arrays with a single element gracefully.