Scale Engineer

Defuse the Bomb

Easy
#1516Time: O(n * |k|) - There is an outer loop that runs `n` times, and for each iteration, a nested loop runs `|k|` times to calculate the sum. This results in a quadratic time complexity relative to the input size and `k`.Space: O(n) - An additional array of size `n` is required to store the decrypted code. If the output array is not considered extra space, the complexity is O(1).
Patterns
Sliding Window
Data structures
Array

Prompt

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.

  • If k > 0, replace the ith number with the sum of the next k numbers.
  • If k < 0, replace the ith number with the sum of the previous k numbers.
  • If 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.length
  • 1 <= n <= 100
  • 1 <= code[i] <= 100
  • -(n - 1) <= k <= n - 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly implements the logic described in the problem statement. It iterates through each element of the code array. For each element at index i, it then performs a second loop to sum up the required k elements, either forward or backward, depending on the sign of k. The circular nature of the array is handled using the modulo operator.

Algorithm

  • Create a result array decryptedCode of size n.
  • If k == 0, return an array of n zeros, as the problem states to replace every number with 0.
  • Loop for i from 0 to n-1 to calculate the value for each position in the decryptedCode.
    • Initialize a variable sum = 0.
    • If k > 0:
      • Start a nested loop for j from 1 to k.
      • In each iteration, find the index of the next element using (i + j) % n to handle the circular nature of the array.
      • Add code[(i + j) % n] to sum.
    • Else if k < 0:
      • Let absK = -k.
      • Start a nested loop for j from 1 to absK.
      • Find the index of the previous element using (i - j + n) % n. Adding n before the modulo operation ensures the result is always non-negative, correctly handling wrap-around.
      • Add code[(i - j + n) % n] to sum.
    • After the inner loop, assign the calculated sum to decryptedCode[i].
  • After the outer loop completes, return the decryptedCode array.

Walkthrough

The algorithm begins by handling the simple case where k is 0, in which it returns an array filled with zeros. For non-zero k, it initializes a result array of the same size as code. It then iterates through each index i of the code array. Inside this loop, it calculates the sum for result[i].

If k is positive, a nested loop runs k times to sum the next k elements. The indices are wrapped around using the modulo operator (% n). For example, the sum for result[i] is code[(i+1)%n] + code[(i+2)%n] + ... + code[(i+k)%n].

If k is negative, a similar nested loop runs |k| times to sum the previous |k| elements. To handle negative indices from subtraction, the formula (i - j + n) % n is used to ensure the index correctly wraps around from the beginning to the end of the array. After computing the sum for index i, it's stored in the result array, and the process continues for the next index.

public int[] decrypt(int[] code, int k) {    int n = code.length;    int[] decryptedCode = new int[n];     if (k == 0) {        return decryptedCode; // Already initialized to all zeros    }     for (int i = 0; i < n; i++) {        int sum = 0;        if (k > 0) {            for (int j = 1; j <= k; j++) {                sum += code[(i + j) % n];            }        } else { // k < 0            int absK = -k;            for (int j = 1; j <= absK; j++) {                // Add n before taking modulo to handle negative results correctly                int prevIndex = (i - j + n) % n;                sum += code[prevIndex];            }        }        decryptedCode[i] = sum;    }     return decryptedCode;}

Complexity

Time

O(n * |k|) - There is an outer loop that runs `n` times, and for each iteration, a nested loop runs `|k|` times to calculate the sum. This results in a quadratic time complexity relative to the input size and `k`.

Space

O(n) - An additional array of size `n` is required to store the decrypted code. If the output array is not considered extra space, the complexity is O(1).

Trade-offs

Pros

  • Simple to understand and implement as it's a direct translation of the problem's requirements.

Cons

  • Inefficient due to redundant calculations. For each element, it re-calculates the sum of a window of k elements, even though adjacent windows have many overlapping elements.

Solutions

class Solution { public int [] decrypt ( int [] code , int k ) { int n = code . length ; int [] ans = new int [ n ]; if ( k == 0 ) { return ans ; } for ( int i = 0 ; i < n ; ++ i ) { if ( k > 0 ) { for ( int j = i + 1 ; j < i + k + 1 ; ++ j ) { ans [ i ] += code [ j % n ]; } } else { for ( int j = i + k ; j < i ; ++ j ) { ans [ i ] += code [( j + n ) % n ]; } } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem