You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code of length of n and a key k.
To decrypt the code, you must replace every number. All the numbers are replaced simultaneously.
k > 0, replace the ith number with the sum of the next k numbers.k < 0, replace the ith number with the sum of the previous k numbers.k == 0, replace the ith number with 0.As code is circular, the next element of code[n-1] is code[0], and the previous element of code[0] is code[n-1].
Given the circular array code and an integer key k, return the decrypted code to defuse the bomb!
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 zero, 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, 2+3, 4+2, 9+4]. Notice that the numbers wrap around again. If k is negative, the sum is of the previous numbers.
Constraints:
n == code.length1 <= n <= 1001 <= code[i] <= 100-(n - 1) <= k <= n - 1Problem Overview: You are given a circular array code and an integer k. Each element must be replaced by the sum of the next k elements if k > 0, the previous |k| elements if k < 0, or 0 if k == 0. Because the array is circular, indices wrap around the end.
The key challenge is handling the circular nature efficiently while computing multiple range sums.
Approach 1: Brute Force Iteration (O(n * |k|) time, O(n) space)
The straightforward solution iterates through every index and manually sums the required k neighbors. For each position i, run another loop that adds the next or previous |k| elements while applying modulo arithmetic to wrap around the array. This guarantees correctness and is easy to implement, especially when first understanding the circular behavior.
The downside is repeated work. Each element recomputes a sum from scratch, leading to O(n * |k|) time complexity. When k approaches n, performance degrades significantly. Space complexity remains O(n) because a separate result array is required. This approach mainly serves as a baseline before optimizing.
Approach 2: Two-Pointer Sliding Window Technique (O(n) time, O(1) extra space)
The optimal solution treats the required k elements as a sliding window over the circular array. Instead of recomputing each sum, maintain a running window sum and shift the window by one position at every step.
If k > 0, initialize a window covering indices 1 through k. If k < 0, build the window from n-|k| through n-1. After computing the first window sum, move both window boundaries forward using two pointers while updating the sum: subtract the element leaving the window and add the new element entering it. Use modulo arithmetic to keep indices within bounds of the circular array.
This technique avoids redundant summation. Each element enters and leaves the window exactly once, producing O(n) time complexity and O(1) auxiliary space beyond the output array. The pattern is a classic application of Sliding Window optimization on a circular Array. Managing the boundaries with two pointers makes the transitions predictable and efficient.
Recommended for interviews: Start by describing the brute force method to demonstrate understanding of the circular indexing rules. Then move to the sliding window optimization. Interviewers typically expect the O(n) two-pointer solution because it eliminates repeated work and shows familiarity with sliding window patterns applied to circular arrays.
This approach uses a sliding window technique to efficiently calculate the sum of required elements. By maintaining a running sum for the window and updating it as you slide, you can achieve the necessary transformation in linear time. The key is to account for the circular nature of the array using modulo operations to wrap around indices.
The C solution implements a sliding window technique. We first determine the starting and ending indices of the window based on the sign of k. For k > 0, the window slides to the right, and for k < 0, we slide to the left by transforming into a positive index shift using modulo operations. This avoids reconstructing the window repeatedly.
Time Complexity: O(n), where n is the length of the `code` array. Each element is processed once with constant-time window updates.
Space Complexity: O(1) auxiliary space (excluding the output array).
This approach is straightforward but less efficient, involving a direct sum computation for each index by wrapping around using the modulo operator. Each element's circular context is individually recalculated, following conditions for the sign of k.
The C implementation iterates over each element in the code for every ith position, calculating indices either forward or backward with the consideration of code's circular nature via modulus operation. Simple yet clear, this needs careful attention to negative index wrapping.
Time Complexity: O(n*k) with n as length of `code` and k an absolute value.
Space Complexity: O(1) extra space beyond output.
We define an answer array ans of length n, initially all elements are 0. According to the problem, if k is 0, return ans directly.
Otherwise, we traverse each position i:
k is a positive number, then the value at position i is the sum of the values at the k positions after position i, that is:$
ans[i] = sum_{j=i+1}^{i+k} code[j bmod n]
k is a negative number, then the value at position i is the sum of the values at the |k| positions before position i, that is:
ans[i] = sum_{j=i+k}^{i-1} code[(j+n) bmod n]
The time complexity is O(n times |k|), ignoring the space consumption of the answer, the space complexity is O(1)$.
Python
Java
C++
Go
TypeScript
In Solution 1, for each position i, we need to traverse k positions, which involves a lot of repeated calculations. We can optimize this by using prefix sums.
We duplicate the code array (this can be achieved without actually duplicating the array, but by cyclically traversing with modulo operation), resulting in an array of twice the length. We then calculate the prefix sum of this array, resulting in a prefix sum array s of length 2 times n + 1.
If k is a positive number, then the value at position i is the sum of the values at the k positions after position i, i.e., ans[i] = s[i + k + 1] - s[i + 1].
If k is a negative number, then the value at position i is the sum of the values at the |k| positions before position i, i.e., ans[i] = s[i + n] - s[i + k + n].
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the code array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Two-Pointer Sliding Window Technique | Time Complexity: O(n), where n is the length of the `code` array. Each element is processed once with constant-time window updates. |
| Brute Force Approach | Time Complexity: O(n*k) with n as length of `code` and k an absolute value. |
| Simulation | — |
| Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Iteration | O(n * |k|) | O(n) | Useful as a baseline or when constraints are very small and clarity matters more than optimization. |
| Two-Pointer Sliding Window | O(n) | O(1) extra | Best choice for large arrays. Efficiently maintains a running sum while moving a circular window. |
Defuse the Bomb - Leetcode 1652 - Python • NeetCodeIO • 14,888 views views
Watch 9 more video solutions →Practice Defuse the Bomb with our built-in code editor and test cases.
Practice on FleetCode