1652. Defuse the Bomb - Detailed Explanation

Problem Statement

You are given a circular array of integers code of length n and an integer k. You want to replace each element code[i] with the sum of k numbers next to it if k > 0, or the sum of k numbers previous to it if k < 0, wrapping around the circle. If k == 0, replace every element with 0.

More formally, let ans be an array of length n. For each index i (0 ≤ i < n):

• If k > 0,

  ans[i] = code[(i+1) % n] + code[(i+2) % n] + … + code[(i+k) % n]
  

• If k < 0,

  ans[i] = code[(i-1+n) % n] + code[(i-2+n) % n] + … + code[(i+k+n) % n]
  

• If k == 0,

  ans[i] = 0
  

Return the array ans.

Examples

Example 1

Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation:
ans[0] = 7 + 1 + 4 = 12
ans[1] = 1 + 4 + 5 = 10 (wrap around)
ans[2] = 4 + 5 + 7 = 16
ans[3] = 5 + 7 + 1 = 13

Example 2

Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]

Example 3

Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation:
ans[0] = code[-1] + code[-2] = 3 + 9 = 12
ans[1] = code[0]  + code[-1] = 2 + 3 = 5
ans[2] = code[1]  + code[0]  = 4 + 2 = 6
ans[3] = code[2]  + code[1]  = 9 + 4 = 13

Constraints

• n == code.length
• 1 ≤ n ≤ 10⁴
• 1 ≤ code[i] ≤ 10⁵
• -10⁴ ≤ k ≤ 10⁴

Brute‑Force Approach

For each index i, sum up the required k neighbours directly, performing k additions per index. Wrap indices using modulo arithmetic.

for i in 0…n-1:
  sum = 0
  if k > 0:
    for j in 1…k: sum += code[(i + j) % n]
  else if k < 0:
    for j in 1…|k|: sum += code[(i - j + n) % n]
  ans[i] = sum

• Time Complexity: O(n × |k|) → in worst case O(n²) if |k| ~ n
• Space Complexity: O(1) extra (O(n) output)

This is too slow when both n and |k| are large.

Optimized Sliding‑Window Approach

Observe that for k > 0, as you move from i to i+1, you remove code[(i+1) % n] from your window and add code[(i+k+1) % n]. Similarly for k < 0, you slide backwards.

Algorithm for k > 0

1. Compute the sum of the first k elements after index 0:

   window = code[1] + code[2] + … + code[k]
   ans[0] = window
   

2. For each i from 1 to n−1:

   window = window - code[(i + 0) % n] + code[(i + k) % n]
   ans[i] = window
   

Algorithm for k < 0

Flip perspective: let K = |k|. Sum the K elements before index 0 (wrapping). Then slide similarly: 1.

window = code[n-1] + code[n-2] + … + code[n-K]
ans[0] = window

2. For each i from 1 to n−1:

   window = window - code[(i - 1 - K + n*X) % n] + code[(i - 1 + n) % n]
   ans[i] = window
   

Here X is chosen so the index stays non‑negative before modulo. In practice you can keep all indices mod n.

Handling k == 0

Simply fill ans with zeros.

Complexity Analysis

• Time: O(n) — each index does O(1) work after initializing the first window
• Space: O(n) for the answer array

Step‑by‑Step Walkthrough (k > 0)

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

1. Initial window for i=0: sum of next 3 = 7+1+4 = 12 → ans[0]=12

2. i=1: remove code[1] (7), add code[(1+3)%4=0] (5) → window = 12−7+5 = 10 → ans[1]=10

3. i=2: remove code[2] (1), add code[(2+3)%4=1] (7) → window = 10−1+7 = 16 → ans[2]=16

4. i=3: remove code[3] (4), add code[(3+3)%4=2] (1) → window = 16−4+1 = 13 → ans[3]=13

Common Mistakes

• Mis‑wrapping indices: forgetting to add n before taking % n for negative values
• Recomputing the full sum inside the loop instead of sliding the window
• Off‑by‑one when determining which elements to subtract/add

Edge Cases

• k == 0: all zeros

• |k| == n: window covers entire array → every ans[i] is the sum of all other elements (or all elements if including self)

• n == 1: trivial, if k≠0 you keep adding the single element repeatedly

Code Solutions

Python

Java Code