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 - 1This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n*k) with n as length of `code` and k an absolute value.
Space Complexity: O(1) extra space beyond output.
| 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. |
Defuse the Bomb - Leetcode 1652 - Python • NeetCodeIO • 10,623 views views
Watch 9 more video solutions →Practice Defuse the Bomb with our built-in code editor and test cases.
Practice on FleetCode