LeetCode Solutions Blog

Defuse the Bomb

Number: 1755

Difficulty: Easy

Paid? No

Problem Description

Given a circular array called code and an integer key k, replace every number in the array simultaneously. If k > 0, replace the ith number with the sum of the next k numbers. If k < 0, replace it with the sum of the previous |k| numbers. If k == 0, replace it with 0. The circular nature means the array wraps around at the edges.

Key Insights

The wrap-around (circular nature) is handled using modulo operations.
For k > 0, a sliding window that sums the next k elements can be used.
For k < 0, a similar sliding window computes the sum of previous |k| elements.
If k is zero, the answer is an array of zeros.
The array size is small enough (n ≤ 100) that even an O(n*|k|) approach is acceptable, though sliding window techniques help reduce redundant computations.

Space and Time Complexity

Time Complexity: O(n * |k|) when using a direct computation, or O(n) if using an optimized sliding window approach. Space Complexity: O(n) due to the output array.

Solution

The solution uses a sliding window strategy. Depending on whether k is positive or negative, we build an initial window sum by summing either the next k elements or the previous |k| elements (using modulo arithmetic). Then, for each index in the array, we update the window by subtracting the element going out of the window and adding the new element entering the window. This way, we avoid recalculating the sum for every index from scratch. For k == 0, we simply return an array of zeros.

Code Solutions

# Python solution for Defuse the Bomb

def decrypt(code, k):
    n = len(code)
    # If k equals 0, return an array of zeros
    if k == 0:
        return [0] * n

    result = [0] * n
    
    # When k is positive, compute the sum of the next k elements using a sliding window
    if k > 0:
        # Compute the initial window sum from the element after index 0 wrapping around
        window_sum = sum(code[(i + 1) % n] for i in range(k))
        for i in range(n):
            result[i] = window_sum
            # Subtract the element that's leaving the window
            window_sum -= code[(i + 1) % n]
            # Add the new element entering the window
            window_sum += code[(i + k + 1) % n]
    else:
        # For k negative, let k_abs be |k|
        k_abs = -k
        # Compute window sum for previous k elements for index 0.
        window_sum = sum(code[(0 - d) % n] for d in range(1, k_abs + 1))
        for i in range(n):
            result[i] = window_sum
            # Update the window:
            # Remove the element that is no longer in the previous window of index i+1.
            window_sum -= code[(i - k_abs) % n]
            # Add the current element which becomes the newest previous element for index i+1.
            window_sum += code[i]
    
    return result

# Example Usage:
print(decrypt([5,7,1,4], 3))  # Expected output: [12,10,16,13]
print(decrypt([1,2,3,4], 0))  # Expected output: [0,0,0,0]
print(decrypt([2,4,9,3], -2)) # Expected output: [12,5,6,13]