LeetCode 1652 - Defuse the Bomb

The problem gives us a circular array called code and an integer k. We must produce a new array where each element is replaced according to the value of k. If k 0, each element becomes the sum of the next k elements in the circular array.

leetcodeeasyarraysliding-window

LeetCode Problem 1652

Difficulty: 🟢 Easy
Topics: Array, Sliding Window

Solution

Problem Understanding

The problem gives us a circular array called code and an integer k. We must produce a new array where each element is replaced according to the value of k.

If k > 0, each element becomes the sum of the next k elements in the circular array.

If k < 0, each element becomes the sum of the previous |k| elements.

If k == 0, every element becomes 0.

The important detail is that the array is circular. This means moving past the end wraps back to the beginning, and moving before the beginning wraps to the end.

For example, with:

code = [5,7,1,4]
k = 3

the first element 5 is replaced with:

7 + 1 + 4 = 12

The second element 7 is replaced with:

1 + 4 + 5 = 10

because after index 3, we wrap around to index 0.

The constraints are small:

  • 1 <= n <= 100
  • 1 <= code[i] <= 100

This means even an O(n^2) solution would technically pass. However, the problem is designed to practice sliding window techniques, so we should still aim for an efficient implementation.

Several edge cases are important:

  • k == 0, every output value must be 0
  • k > 0, we must correctly wrap around the array
  • k < 0, we must correctly move backward and wrap around
  • Arrays with length 1
  • Values of k close to n - 1

A naive implementation can easily make off-by-one mistakes when wrapping indices.

Approaches

Brute Force Approach

The most straightforward solution is to compute each result independently.

For every index i:

  • If k > 0, iterate through the next k elements and sum them.
  • If k < 0, iterate through the previous |k| elements and sum them.
  • Use modulo arithmetic to wrap around the circular array.

This approach is easy to understand and directly follows the problem statement.

For each of the n elements, we may scan up to |k| elements. Since |k| can be as large as n - 1, the total complexity becomes O(n^2).

Although this is acceptable for the given constraints, we can do better.

Optimal Sliding Window Approach

The key observation is that neighboring windows overlap heavily.

Suppose k > 0.

If we already know the sum of the next k numbers for index i, then for index i + 1:

  • One element leaves the window
  • One new element enters the window

Instead of recomputing the whole sum, we can update it in constant time.

This is exactly the sliding window technique.

The same logic works for k < 0, except the window moves differently.

By maintaining a running sum of the current window, we reduce the time complexity to O(n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Recomputes every sum independently
Optimal O(n) O(n) Uses a sliding window to reuse previous computations

Algorithm Walkthrough

Optimal Sliding Window Algorithm

  1. First, handle the special case where k == 0.

If k is zero, every element becomes 0, so we immediately return an array of zeros. 2. Create a result array of length n.

This array will store the decrypted values. 3. Determine the initial sliding window boundaries.

If k > 0:

  • The first window contains indices 1 through k
  • These are the next k elements after index 0

If k < 0:

  • The first window contains the previous |k| elements
  • These correspond to indices n - |k| through n - 1
  1. Compute the initial window sum.

This gives the decrypted value for index 0. 5. Iterate through every index i from 0 to n - 1.

For each position:

  • Store the current window sum into result[i]
  • Slide the window forward by one position
  1. Update the sliding window efficiently.

To move the window:

  • Subtract the element leaving the window
  • Add the new element entering the window
  • Use modulo arithmetic to wrap around the circular array
  1. Continue until every position has been processed.

Why it works

The algorithm maintains the invariant that the sliding window always contains exactly the elements needed for the current index.

When moving from one index to the next, the required set of elements changes by only one outgoing element and one incoming element. Updating the running sum preserves correctness while avoiding repeated work.

Because every window is updated consistently and modulo arithmetic correctly handles wrapping, every result is computed accurately.

Python Solution

from typing import List

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)

        if k == 0:
            return [0] * n

        result = [0] * n

        if k > 0:
            left = 1
            right = k
        else:
            left = n + k
            right = n - 1

        window_sum = 0

        for i in range(left, right + 1):
            window_sum += code[i % n]

        for i in range(n):
            result[i] = window_sum

            window_sum -= code[left % n]
            left += 1

            right += 1
            window_sum += code[right % n]

        return result

The implementation starts by handling the k == 0 case separately because no sliding window is needed.

For positive k, the initial window consists of the next k elements after index 0.

For negative k, the initial window contains the previous |k| elements before index 0.

The variables left and right represent the boundaries of the current window. The initial window sum is computed once.

During each iteration:

  • The current window sum is assigned to the answer
  • The leftmost element is removed
  • The window boundaries move one step forward
  • The new rightmost element is added

Modulo arithmetic ensures circular behavior.

Go Solution

func decrypt(code []int, k int) []int {
    n := len(code)

    if k == 0 {
        return make([]int, n)
    }

    result := make([]int, n)

    left, right := 0, 0

    if k > 0 {
        left = 1
        right = k
    } else {
        left = n + k
        right = n - 1
    }

    windowSum := 0

    for i := left; i <= right; i++ {
        windowSum += code[i%n]
    }

    for i := 0; i < n; i++ {
        result[i] = windowSum

        windowSum -= code[left%n]
        left++

        right++
        windowSum += code[right%n]
    }

    return result
}

The Go implementation follows the same logic as the Python version.

A slice is used for the result array. Since the constraints are small, standard int arithmetic is completely safe and no overflow concerns exist.

Go does not support Python-style negative indexing, so all wrapping is handled explicitly using modulo arithmetic.

Worked Examples

Example 1

code = [5,7,1,4]
k = 3

Initial window for index 0:

[7,1,4]
sum = 12
Iteration Window Elements Window Sum Result
i = 0 [7,1,4] 12 result[0] = 12
i = 1 [1,4,5] 10 result[1] = 10
i = 2 [4,5,7] 16 result[2] = 16
i = 3 [5,7,1] 13 result[3] = 13

Final result:

[12,10,16,13]

Example 2

code = [1,2,3,4]
k = 0

Since k == 0, every value becomes 0.

Result:

[0,0,0,0]

Example 3

code = [2,4,9,3]
k = -2

For index 0, we sum the previous two elements:

[9,3]
sum = 12
Iteration Window Elements Window Sum Result
i = 0 [9,3] 12 result[0] = 12
i = 1 [3,2] 5 result[1] = 5
i = 2 [2,4] 6 result[2] = 6
i = 3 [4,9] 13 result[3] = 13

Final result:

[12,5,6,13]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element enters and leaves the sliding window once
Space O(n) The output array requires linear space

The sliding window allows each update to happen in constant time. Instead of recomputing sums repeatedly, we reuse previous work by removing one value and adding one value per step.

Test Cases

from typing import List

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)

        if k == 0:
            return [0] * n

        result = [0] * n

        if k > 0:
            left = 1
            right = k
        else:
            left = n + k
            right = n - 1

        window_sum = 0

        for i in range(left, right + 1):
            window_sum += code[i % n]

        for i in range(n):
            result[i] = window_sum

            window_sum -= code[left % n]
            left += 1

            right += 1
            window_sum += code[right % n]

        return result

sol = Solution()

assert sol.decrypt([5,7,1,4], 3) == [12,10,16,13]  # provided positive k example
assert sol.decrypt([1,2,3,4], 0) == [0,0,0,0]  # k equals zero
assert sol.decrypt([2,4,9,3], -2) == [12,5,6,13]  # provided negative k example

assert sol.decrypt([10], 0) == [0]  # single element array
assert sol.decrypt([1,2], 1) == [2,1]  # smallest positive window
assert sol.decrypt([1,2], -1) == [2,1]  # smallest negative window

assert sol.decrypt([1,2,3,4,5], 4) == [14,13,12,11,10]  # k equals n - 1
assert sol.decrypt([1,2,3,4,5], -4) == [14,13,12,11,10]  # negative k near limit

assert sol.decrypt([100,100,100], 2) == [200,200,200]  # large values
assert sol.decrypt([3,6,9], 1) == [6,9,3]  # simple wrap around
assert sol.decrypt([3,6,9], -1) == [9,3,6]  # backward wrap around
Test Why
[5,7,1,4], k=3 Standard positive sliding window
[1,2,3,4], k=0 Special zero case
[2,4,9,3], k=-2 Negative window movement
[10], k=0 Single-element edge case
[1,2], k=1 Minimal positive wrap
[1,2], k=-1 Minimal negative wrap
[1,2,3,4,5], k=4 Maximum positive window size
[1,2,3,4,5], k=-4 Maximum negative window size
[100,100,100], k=2 Large element values
[3,6,9], k=1 Forward circular wrapping
[3,6,9], k=-1 Backward circular wrapping

Edge Cases

One important edge case is when k == 0. A common mistake is to still attempt sliding window logic, which can create invalid ranges or incorrect sums. The implementation handles this immediately by returning an array filled with zeros.

Another tricky case is negative k. Moving backward in a circular array is more error-prone because indices can become negative. The implementation avoids negative indexing entirely by carefully defining the initial window and always using modulo arithmetic.

A third important edge case occurs when |k| is close to n - 1. In these situations, the window nearly spans the entire array. Incorrect window updates can accidentally include or exclude the current element. The implementation maintains precise left and right boundaries so the window always contains exactly the required elements.

Arrays of size 1 are also worth considering. The constraints guarantee that if n == 1, then k must be 0, because -(n - 1) <= k <= n - 1. The implementation naturally handles this case correctly by returning [0].