# Defuse the Bomb
**Difficulty:** EASY
[External](https://leetcode.com/problems/defuse-the-bomb)
Canonical: https://scaleengineer.com/dsa/problems/defuse-the-bomb
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array
---
## Problem
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
## Brute Force Simulation
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.
**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).
**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.
### Explanation
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.

```java
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;
}
```
### 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.

## Sliding Window Optimization
This approach optimizes the brute-force method by using a sliding window technique. It recognizes that the sum for an element at index `i` is highly related to the sum for the element at `i-1`. Instead of re-calculating the sum from scratch for each element, we can compute the first sum and then 'slide' the window one position at a time. In each step, we update the sum by subtracting the element that leaves the window and adding the new element that enters it. This reduces the time complexity from O(n*k) to O(n).
**Time:** O(n) - The initial sum calculation takes O(|k|) time. The main loop then runs `n-1` times, with each step taking O(1) time. The total time is O(|k| + n). Since the problem constraints state `|k| < n`, this simplifies to O(n). · **Space:** O(n) - A result array of size `n` is needed. The implementation shown uses an auxiliary array of size `2n`, but this can be avoided by using modulo arithmetic, keeping the space complexity dominated by the O(n) output array.
**Pros:** Highly efficient with a linear time complexity, making it suitable for larger inputs.; It's the optimal solution for this problem.
**Cons:** The logic is slightly more complex to devise compared to the brute-force approach, especially for handling the indices correctly.; The version with a doubled temporary array uses more space, although it simplifies the code.
### Explanation
The sliding window approach avoids redundant computations. First, the sum for the window corresponding to the first element (`result[0]`) is calculated. This takes O(|k|) time. Then, the algorithm iterates from `i = 1` to `n-1`. For each `i`, the sum for `result[i]` is derived from the sum for `result[i-1]` in constant time.

For `k > 0`, the window for `result[i]` is `[i+1, ..., i+k]`. This window is obtained by sliding the window for `result[i-1]` (which was `[i, ..., i+k-1]`) one step forward. So, the new sum is `previous_sum - code[i] + code[i+k]`.

For `k < 0`, a similar logic applies. The window of previous elements also slides forward as `i` increases.

To make handling the circular array easier, a common technique is to create a temporary array of size `2n` by appending `code` to itself. This allows us to access wrapped-around elements using simple array indexing without the modulo operator in the main loop, leading to cleaner code.

```java
public int[] decrypt(int[] code, int k) {
    int n = code.length;
    int[] result = new int[n];

    if (k == 0) {
        return result;
    }

    // Double the array to easily handle circularity
    int[] newCode = new int[2 * n];
    System.arraycopy(code, 0, newCode, 0, n);
    System.arraycopy(code, 0, newCode, n, n);

    int sum = 0;
    if (k > 0) {
        // Initial window for result[0] is from index 1 to k
        for (int i = 1; i <= k; i++) {
            sum += newCode[i];
        }
        result[0] = sum;
        // Slide the window for the rest
        for (int i = 1; i < n; i++) {
            sum = sum - newCode[i] + newCode[i + k];
            result[i] = sum;
        }
    } else { // k < 0
        int absK = -k;
        // Initial window for result[0] is from index n-absK to n-1
        for (int i = n - absK; i < n; i++) {
            sum += newCode[i];
        }
        result[0] = sum;
        // Slide the window for the rest
        for (int i = 1; i < n; i++) {
            // The element leaving is at index (n+i-1-absK)
            // The element entering is at index (n+i-1)
            sum = sum - newCode[n + i - 1 - absK] + newCode[n + i - 1];
            result[i] = sum;
        }
    }
    return result;
}
```
### Algorithm
- Handle the `k == 0` case by returning an array of `n` zeros.
- To simplify circular array indexing, create a temporary array `newCode` of size `2n` by concatenating `code` with itself.
- Initialize a `sum` variable for the sliding window.
- If `k > 0`:
    - Calculate the initial sum for `result[0]` by summing elements from `newCode[1]` to `newCode[k]`. Store it in `result[0]`.
    - Loop `i` from `1` to `n-1`.
    - Update the `sum` in O(1) by subtracting the element that leaves the window (`newCode[i]`) and adding the element that enters (`newCode[i + k]`).
    - Store the updated `sum` in `result[i]`.
- If `k < 0`:
    - Let `absK = -k`.
    - Calculate the initial sum for `result[0]` by summing elements from `newCode[n - absK]` to `newCode[n - 1]`. Store it in `result[0]`.
    - Loop `i` from `1` to `n-1`.
    - Update the `sum` by subtracting the element leaving the window (`newCode[n + i - 1 - absK]`) and adding the one entering (`newCode[n + i - 1]`).
    - Store the updated `sum` in `result[i]`.
- Return the `result` array.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution { public: vector < int > decrypt ( vector < int >& code , int k ) { int n = code . size (); vector < int > ans ( 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 ; } };
```

### Python

```python
class Solution : def decrypt ( self , code : List [ int ], k : int ) -> List [ int ]: n = len ( code ) ans = [ 0 ] * n if k == 0 : return ans for i in range ( n ): if k > 0 : for j in range ( i + 1 , i + k + 1 ): ans [ i ] += code [ j % n ] else : for j in range ( i + k , i ): ans [ i ] += code [( j + n ) % n ] return ans
```