1652. Defuse the Bomb
Problem Description
You are tasked with decrypting a circular array of numbers (code
) given a specific integer key (k
). The array is circular, which means that after the last element, it loops back to the first element, and before the first element, it loops back to the last element. To decrypt the array, you need to transform each element following these rules:
- If
k
is greater than 0, replace each element with the sum of the nextk
elements. - If
k
is less than 0, replace each element with the sum of the previousk
elements (sincek
is negative, you're summing the-k
elements that come before). - If
k
equals 0, replace each element with 0.
The challenge is to perform this decryption and return the new array that represents the defused bomb's code.
Intuition
To solve this problem, we need to simulate the process of replacing each number in the circular array based on the value of k
. Since the array is circular, we will have to handle the wrap-around when k
is positive or negative.
The straightforward approach would involve iterating through the array for each element and then summing the next or previous k
elements depending on the sign of k
. However, doing this would require careful handling of the indices to avoid going out of bounds and to wrap around when needed.
A more efficient solution is to make use of prefix sums to quickly calculate the sum of any subarray. Prefix sums allow us to sum a range of elements in constant time once the prefix sums array is computed. We can do this by creating a new array that is twice the size of the original array and is a concatenation of two copies of the original array (code + code
). This way, we can simplify the indexing for the wrap-around without having to mod the index each time.
The prefix sums are calculated using the Python function accumulate
with an initial=0
value. This constructs an array s
where s[i]
represents the sum of the first i
elements in the extended array.
When k
is positive, we take the sum of the subarray that starts just after the current element and extends k
elements forward.
When k
is negative, we need to take the sum of the subarray that starts k
elements before the current element and goes up to just before the current element.
Because we are using prefix sums, we calculate these subarray sums by subtracting the appropriate prefix sums:
- If
k > 0
,ans[i] = s[i + k + 1] - s[i + 1]
. - If
k < 0
,ans[i] = s[i + n] - s[i + k + n]
.
Finally, for k == 0
, we simply return an array filled with zeros.
Using prefix sums and the doubled array trick to handle the circular nature of the problem, we achieve a solution that is efficient and avoids complicated index wrangling.
Solution Approach
To implement the solution, we leverage a well-known algorithmic pattern: the prefix sum array. This array stores the cumulative sums of the elements in an array, allowing fast computation of the sum of any subarray. The solution involves the following steps:
-
Create an Extended Array: We initiate by creating an array
s
that's twice as long as the input arraycode
, achieved by concatenatingcode
with itself (code + code
). This simplifies our calculations for the circular array since we won't need to manually wrap around the array's ends. -
Calculate Prefix Sums: Using the
accumulate
function with aninitial=0
, we compute the prefix sums for our extended array. The result is thats[i]
contains the sum of the elements up to, but not including, positioni
in the extended array. -
Initialize Answer Array: We initialize an array
ans
of the same length ascode
with all elements set to 0. This array will store our decrypted code numbers. -
Handle k == 0: If
k
is zero, we know that each element in the array simply becomes 0. Since we've already initializedans
to all zeros, we can return it directly without any additional computation. -
Compute Decrypted Values:
- If
k > 0
: For each indexi
in the original array range (from 0 ton - 1
), we replace the element with the sum of the nextk
elements. To do this without manually calculating the sum each time, we take advantage of our prefix sums arrays
. We calculateans[i]
as the difference betweens[i + k + 1]
ands[i + 1]
. This gives us the sum of thek
elements following indexi
. - If
k < 0
: We do something similar but for the previousk
elements. Sincek
is negative, to get-k
previous elements, we calculateans[i]
as the difference betweens[i + n]
ands[i + k + n]
. This is equivalent to summing the elements from indexi + k
(inclusive) up toi
(exclusive) in the circular array.
- If
-
Return the Answer: After computing the new values for all
i
, we return theans
array as the final decrypted code.
The algorithm's time complexity is O(n)
where n
is the length of the code
array because each element is processed in a constant amount of time due to the precomputed prefix sums.
This solution is not only efficient but also elegant, as it reduces a problem involving potentially complex modular arithmetic and handling of circular array indices to simple array accesses and subtraction operations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution mentioned in the content provided.
Suppose we have a circular array code
with elements [5, 7, 1, 4]
and we are given an integer key k = 3
. Here's how we would decrypt the array following the solution approach:
-
Create an Extended Array: We first concatenate the array
code
with itself. So the extended arrays
becomes[5, 7, 1, 4, 5, 7, 1, 4]
. -
Calculate Prefix Sums: Using the prefix sums concept, we calculate the sums as follows:
[0, 5, 12, 13, 17, 22, 29, 30, 34]
The array starts with
0
because initially, there's nothing to sum. -
Initialize Answer Array: We prepare an answer array
ans
with the same length ascode
and initialize it with zeros:[0, 0, 0, 0]
. -
Handle k == 0: In this case,
k
is not 0, so we proceed to the next step. -
Compute Decrypted Values: Since
k > 0
, we update each element ofans
as follows:- For
i = 0
(corresponding to element5
), the sum of the nextk = 3
elements iss[0 + 3 + 1] - s[0 + 1]
, which iss[4] - s[1]
=17 - 5
=12
. So,ans[0]
becomes12
. - For
i = 1
(corresponding to element7
), the sum iss[1 + 3 + 1] - s[1 + 1]
, which iss[5] - s[2]
=22 - 12
=10
. So,ans[1]
becomes10
. - For
i = 2
(corresponding to element1
), the sum iss[2 + 3 + 1] - s[2 + 1]
, which iss[6] - s[3]
=29 - 13
=16
. So,ans[2]
becomes16
. - For
i = 3
(corresponding to element4
), the sum iss[3 + 3 + 1] - s[3 + 1]
, which iss[7] - s[4]
=30 - 17
=13
. So,ans[3]
becomes13
.
- For
-
Return the Answer: The resulting decrypted array is
[12, 10, 16, 13]
.
The time complexity of this approach is O(n)
. The prefix sum array and extending the s
array let us avoid dealing with circular wrap-around through modulus operations, enabling us to calculate each element's sum in constant time.
Solution Implementation
1from typing import List
2from itertools import accumulate
3
4class Solution:
5 def decrypt(self, code: List[int], k: int) -> List[int]:
6 # Get the length of the code list
7 length_of_code = len(code)
8 # Initial answer list filled with zeros
9 decrypted_code = [0] * length_of_code
10
11 # If k is 0, the task is to return a list of the same length filled with zeros
12 if k == 0:
13 return decrypted_code
14
15 # Create a prefix sum array with the code list repeated twice
16 # 'initial=0' is to set the starting value of the accumulation to zero
17 prefix_sum = list(accumulate(code + code, initial=0))
18
19 # Iterate through each element in the code list to compute its decrypted value
20 for i in range(length_of_code):
21 if k > 0:
22 # If k is positive, sum the next k values from the element's position
23 decrypted_code[i] = prefix_sum[i + k + 1] - prefix_sum[i + 1]
24 else:
25 # If k is negative, sum the k values preceding the element's position
26 decrypted_code[i] = prefix_sum[i + length_of_code] - prefix_sum[i + k + length_of_code]
27
28 # Return the decrypted code
29 return decrypted_code
30
1class Solution {
2 public int[] decrypt(int[] code, int k) {
3 int n = code.length; // Length of the code array.
4 int[] answer = new int[n]; // The resultant array after decryption.
5
6 // If k is 0, then the decryption is a zero array of length n.
7 if (k == 0) {
8 return answer;
9 }
10
11 // Create a sum array with size double the code (to handle wrap around) plus one (for easing the prefix sum calculation).
12 int[] sum = new int[n * 2 + 1];
13
14 // Compute the prefix sums for the array.
15 for (int i = 0; i < n * 2; ++i) {
16 sum[i + 1] = sum[i] + code[i % n];
17 }
18
19 // Process each element in the code array.
20 for (int i = 0; i < n; ++i) {
21 // If k is positive, sum the next k elements including the current one.
22 if (k > 0) {
23 answer[i] = sum[i + k + 1] - sum[i + 1];
24 } else {
25 // If k is negative, sum the k elements before the current one.
26 answer[i] = sum[i + n] - sum[i + k + n];
27 }
28 }
29
30 // Return the decrypted code.
31 return answer;
32 }
33}
34
1class Solution {
2public:
3 vector<int> decrypt(vector<int>& code, int k) {
4 int n = code.size(); // Get the size of the code vector
5 vector<int> ans(n, 0); // Initialize the answer vector with `n` zeros
6
7 // If k is zero, no decryption is performed; return the initialized answer
8 if (k == 0) {
9 return ans;
10 }
11
12 // Create a prefix sum array with double the size of the code array plus one
13 // This allows easy calculation over circular arrays
14 vector<int> prefixSum(2 * n + 1, 0);
15
16 // Calculate prefix sums for `code` replicated twice
17 for (int i = 0; i < 2 * n; ++i) {
18 prefixSum[i + 1] = prefixSum[i] + code[i % n];
19 }
20
21 // Decrypt the code based on the value of k
22 for (int i = 0; i < n; ++i) {
23 if (k > 0) {
24 // If k is positive, sum next k elements
25 ans[i] = prefixSum[i + k + 1] - prefixSum[i + 1];
26 } else {
27 // If k is negative, sum previous k elements
28 ans[i] = prefixSum[i + n] - prefixSum[i + k + n];
29 }
30 }
31
32 // Return the decrypted code
33 return ans;
34 }
35};
36
1// Function to decrypt a code array based on an integer k
2// If k is positive, replace every element with the sum of the next k elements
3// If k is negative, replace every element with the sum of the previous -k elements
4// If k is zero, replace every element with 0
5function decrypt(code: number[], k: number): number[] {
6 // Get the number of elements in the code array
7 const codeLength = code.length;
8
9 // If k is 0, fill the entire code array with 0s and return it
10 if (k === 0) {
11 return new Array(codeLength).fill(0);
12 }
13
14 // Determine the direction of the sum based on the sign of k
15 const isNegativeK = k < 0;
16 if (isNegativeK) {
17 k = -k; // Make k positive for easier calculations
18 }
19
20 // Initialize a map to store the sum of elements at each index for prefix and suffix
21 const sumMap = new Map<number, [number, number]>();
22
23 // Calculate the initial prefix and suffix sums
24 let prefixSum = 0;
25 let suffixSum = 0;
26 for (let i = 1; i <= k; i++) {
27 prefixSum += code[codeLength - i];
28 suffixSum += code[i % codeLength];
29 }
30
31 // Store the initial sums in the map
32 sumMap.set(0, [prefixSum, suffixSum]);
33
34 // Calculate and store the prefix and suffix sums for each element
35 for (let i = 1; i < codeLength; i++) {
36 let [previousPrefix, previousSuffix] = sumMap.get(i - 1);
37
38 // Update prefix by subtracting and adding elements at the boundaries
39 previousPrefix -= code[(codeLength - k - 1 + i) % codeLength];
40 previousPrefix += code[(i - 1) % codeLength];
41
42 // Update suffix by subtracting and adding elements at the boundaries
43 previousSuffix -= code[i % codeLength];
44 previousSuffix += code[(i + k) % codeLength];
45
46 // Store the updated sums in the map
47 sumMap.set(i, [previousPrefix, previousSuffix]);
48 }
49
50 // Construct and return the decrypted code array
51 return code.map((_, index) => sumMap.get(index)[isNegativeK ? 0 : 1]);
52}
53
54// Example usage
55const encryptedCode = [5, 7, 1, 4];
56const k = 3;
57const decryptedCode = decrypt(encryptedCode, k);
58console.log(decryptedCode); // Output will be the decrypted code based on the value of k
59
Time and Space Complexity
Time Complexity
The main operations to consider for time complexity are the accumulation of the list and the for loop that iterates over the range (n)
.
accumulate(code + code, initial=0)
: Doubling the listcode
has a time complexity ofO(n)
since it involves copying the elements. Theaccumulate()
function performs a prefix sum operation, which takesO(2n)
time over the doubled list (since the listcode
is appended to itself).- The for loop: This iterates over the list of length
n
and performs constant-time operations inside the loop. No nested loops are present, therefore, this part contributesO(n)
to the time complexity.
Hence, the total time complexity of the code is O(n) + O(2n) + O(n)
which simplifies to O(n)
.
Space Complexity
For space complexity analysis, the additional space used by the algorithm aside from the input and output is considered.
s = list(accumulate(code + code, initial=0))
: It creates a new list from the accumulated sums of the doubled original list. Since the list is doubled in size before accumulating, and an extra element is added due toinitial=0
, the space complexity for this part isO(2n+1)
which simplifies toO(n)
since constant factors and lower-order terms are ignored.ans = [0] * n
: Allocates a list of the same length as the input listcode
. This contributesO(n)
to the space complexity.
Other variables (n
, i
, k
) use constant space and do not scale with the size of the input.
The total space complexity of the code is O(n)
for the accumulated sums list plus O(n)
for the answer list, which simplifies to O(n)
since both are linear terms and we do not multiply complexities when they are of the same order.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!