1. Defuse the Bomb (LeetCode)
Model answer
The task
For each position in a circular array, compute the sum of the next k values when k is positive, or the previous |k| values when k is negative. When k is zero, every result is zero.
Key idea
Maintain the sum of the relevant circular window and update it as the position advances, rather than recalculating each sum. Split |k| into complete cycles and a remainder so the solution also handles values of k larger than the array length.
Approach
- Return an empty list for an empty array, and zeros when
kis zero. - Split
|k|into complete cycles and a remainder; each complete cycle contributes the array’s total sum. - Initialize the remainder window: start after the current position for positive
k, or before it for negativek. - Record each result and slide the window by removing the value that leaves and adding the next value.
from typing import List
class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
n = len(code)
if n == 0:
return []
if k == 0:
return [0] * n
count = abs(k)
cycles, remainder = divmod(count, n)
full_cycle_sum = cycles * sum(code)
result = [0] * n
if k > 0:
# Initial window contains the next `remainder` values.
window = sum(code[j % n] for j in range(1, remainder + 1))
for i in range(n):
result[i] = full_cycle_sum + window
# Advance the window to the next position.
window -= code[(i + 1) % n]
window += code[(i + remainder + 1) % n]
else:
# Initial window contains the previous `remainder` values.
window = sum(code[-j % n] for j in range(1, remainder + 1))
for i in range(n):
result[i] = full_cycle_sum + window
# Advance the window to the next position.
window -= code[(i - remainder) % n]
window += code[i % n]
return result
Complexity:
- Time: O(n), since each window is initialized and updated in constant time per position.
- Space: O(n) for the result; O(1) auxiliary space.
Common follow-ups
- What if
kis zero? Return an array of zeros. - What if
|k|exceeds the array length? Count full cycles separately, as above. - Can the result be produced in place? Only if modifying the input is allowed and its original values remain available during computation.