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
codeof lengthn. - 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.
kcan range from-(n - 1)ton - 1.- If
k == 0, all elements in the output should be0. - 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
-
Initialize Variables:
- Create an output array
resultof the same length ascode. - Calculate the absolute value of
kand store it in a variableabs_k.
- Create an output array
-
Handle k == 0 Case:
- If
kis0, fill the entireresultarray with0s.
- If
-
Sliding Window Technique:
- Initialize a running sum
window_sumto0. - Calculate the initial window sum for the first
abs_kelements. - For each element in the array, update the corresponding position in the
resultarray with the currentwindow_sum. - Slide the window by subtracting the element that is leaving the window and adding the new element entering the window.
- Initialize a running sum
-
Return the Result:
- Return the
resultarray after processing all elements.
- Return the
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
resultof the same length ascode.
- We use an additional array
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
kelements is calculated correctly for each position, wrapping around at the end. - k < 0: The sum of the previous
kelements is calculated correctly for each position, wrapping around at the beginning. - Single Element Array: The function handles arrays with a single element gracefully.