Defuse the Bomb

Difficulty: Easy | Acceptance: 79.30% | Paid: No Topics: Array, Sliding Window

You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code of length n and a key k.

To decrypt the code, you must replace every number in the array with the sum of the next k numbers. Since the array is circular, the next element of code[n-1] is code[0], and the previous element of code[0] is code[n-1].

If k is positive, replace the ith number with the sum of the next k numbers. If k is negative, replace the ith number with the sum of the previous k numbers. If k is 0, replace the ith number with 0.

As the code is circular, the next element of code[n-1] is code[0], and the previous element of code[0] is code[n-1].

Return the decrypted code.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Sliding Window
• Approach 3: Prefix Sum

Examples

Example 1

Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each number is replaced by the sum of the next 3 numbers. The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Notice that the numbers wrap around.

Example 2

Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: When k is 0, the numbers are replaced by 0.

Example 3

Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: The decrypted code is [3+9, 4+3, 2+4, 9+2]. Notice that the previous element of code[0] is code[n-1].

Constraints

n == code.length
1 <= n <= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1

Approach 1: Brute Force

Intuition Iterate through each element of the array. For each element, loop k times to find the subsequent or preceding elements, using modulo arithmetic to handle the circular nature of the array.

Steps

• Initialize a result array of zeros with the same length as code.
• If k is 0, return the result array immediately.
• Iterate through each index i from 0 to n-1.
• Initialize a sum variable to 0.
• Loop j from 1 to abs(k).
• If k > 0, add code[(i + j) % n] to the sum.
• If k < 0, add code[(i - j + n) % n] to the sum.
• Store the calculated sum in result[i].
• Return the result array.

class Solution:
    def decrypt(self, code: list[int], k: int) -> list[int]:
        n = len(code)
        res = [0] * n
        if k == 0:
            return res
        
        for i in range(n):
            total = 0
            for j in range(1, abs(k) + 1):
                if k > 0:
                    total += code[(i + j) % n]
                else:
                    total += code[(i - j + n) % n]
            res[i] = total
        
        return res

Complexity

• Time: O(n × |k|)
• Space: O(n)
• Notes: Simple to implement but inefficient for large inputs, though constraints are small here.

Approach 2: Sliding Window

Intuition Since we are summing a fixed window of size |k| in a circular array, we can slide the window across the array. By adding the new element entering the window and subtracting the element leaving it, we can update the sum in constant time.

Steps

• Handle k = 0 by returning an array of zeros.
• Create an extended array by concatenating code with itself to handle circularity easily.
• Determine the initial window start and end indices based on the sign of k.
• Calculate the sum of the initial window.
• Iterate through the original array indices, storing the current window sum in the result.
• Slide the window by subtracting the element at the start and adding the element at the end, then incrementing start and end.
• Return the result array.

class Solution:
    def decrypt(self, code: list[int], k: int) -> list[int]:
        n = len(code)
        res = [0] * n
        if k == 0:
            return res
        
        extended = code + code
        start = 1 if k > 0 else n + k
        end = start + abs(k)
        window_sum = sum(extended[start:end])
        
        for i in range(n):
            res[i] = window_sum
            window_sum -= extended[start]
            window_sum += extended[end]
            start += 1
            end += 1
            
        return res

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Optimized approach that avoids redundant calculations.

Approach 3: Prefix Sum

Intuition We can precompute the cumulative sum (prefix sum) of the array duplicated twice. This allows us to calculate the sum of any subarray in O(1) time by subtracting two prefix sums.

Steps

• Handle k = 0 by returning an array of zeros.
• Construct a prefix sum array of size 2n + 1 from the duplicated array.
• Iterate through each index i of the original array.
• If k > 0, the sum is prefix[i + k + 1] - prefix[i + 1].
• If k < 0, the sum is prefix[i + n] - prefix[i + n + k].
• Store the result and return the array.

class Solution:
    def decrypt(self, code: list[int], k: int) -> list[int]:
        n = len(code)
        res = [0] * n
        if k == 0:
            return res
        
        prefix = [0] * (2 * n + 1)
        for i in range(2 * n):
            prefix[i + 1] = prefix[i] + code[i % n]
        
        for i in range(n):
            if k > 0:
                res[i] = prefix[i + k + 1] - prefix[i + 1]
            else:
                res[i] = prefix[i + n] - prefix[i + n + k]
        
        return res

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Useful when multiple range sum queries are required on the same array.