Problem Description

You need to defuse a bomb by decrypting a circular array code of length n using a key k.

The decryption process replaces every number in the array simultaneously based on these rules:

• If k > 0: Replace the i-th number with the sum of the next k numbers
• If k < 0: Replace the i-th number with the sum of the previous |k| numbers
• If k == 0: Replace the i-th number with 0

Since the array is circular:

• The next element after code[n-1] is code[0]
• The previous element before code[0] is code[n-1]

For example, if code = [5,7,1,4] and k = 3:

• For index 0: sum the next 3 elements → 7 + 1 + 4 = 12
• For index 1: sum the next 3 elements → 1 + 4 + 5 = 10 (wraps around)
• For index 2: sum the next 3 elements → 4 + 5 + 7 = 16 (wraps around)
• For index 3: sum the next 3 elements → 5 + 7 + 1 = 13 (wraps around)
• Result: [12, 10, 16, 13]

The solution iterates through each position i in the array:

• When k > 0: It calculates ans[i] = sum(code[(i+1) % n] to code[(i+k) % n])
• When k < 0: It calculates ans[i] = sum(code[(i+k) % n] to code[(i-1) % n])

The modulo operator % handles the circular nature of the array, ensuring indices wrap around correctly.

Intuition

The key insight is recognizing that this is a straightforward simulation problem where we need to handle circular array indexing properly.

Since we need to replace all numbers simultaneously, we can't modify the original array in-place. We need a separate result array to store the new values. This ensures that when calculating the sum for position i, we're always using the original values, not the already-replaced ones.

For the circular nature of the array, we can use the modulo operator % to wrap around indices. When we go past the end of the array (index >= n), the modulo operation brings us back to the beginning. For example, if we have an array of length 4 and we're at index 3, the next index would be (3 + 1) % 4 = 0, which correctly wraps to the start.

The three cases are handled separately:

1. When k = 0, every element becomes 0 - this is trivial
2. When k > 0, we sum the next k elements by iterating from i+1 to i+k and using j % n to handle wrapping
3. When k < 0, we sum the previous |k| elements by iterating from i+k (which is negative offset) to i-1, and using (j + n) % n to handle negative indices properly

The reason we add n in the negative case is to convert negative indices to their positive equivalents. For instance, index -1 should map to n-1 (the last element), and (-1 + n) % n = n-1 achieves this.

The time complexity is O(n * |k|) since for each of the n positions, we sum up |k| values. The space complexity is O(n) for the result array.

Learn more about Sliding Window patterns.

Solution Approach

The implementation follows a simulation approach where we process each position in the array and calculate its new value based on the given rules.

First, we initialize an answer array ans of length n with all zeros. This serves as our result array where we'll store the decrypted values.

If k = 0, we immediately return the ans array since all elements should be replaced with 0.

For non-zero values of k, we iterate through each position i from 0 to n-1:

When k > 0:

• We need to sum the next k elements after position i
• We iterate from i + 1 to i + k (inclusive)
• For each position j in this range, we add code[j % n] to ans[i]
• The modulo operation j % n handles the circular wrapping when j >= n

The mathematical formula is:

ans[i] = Σ(j=i+1 to i+k) code[j mod n]

When k < 0:

• We need to sum the previous |k| elements before position i
• We iterate from i + k to i - 1 (inclusive)
• Since k is negative, i + k gives us the starting position |k| positions before i
• For each position j in this range, we add code[(j + n) % n] to ans[i]
• Adding n before taking modulo ensures we handle negative indices correctly

The mathematical formula is:

ans[i] = Σ(j=i+k to i-1) code[(j + n) mod n]

The key technique here is using modular arithmetic to handle the circular array:

• j % n maps any index j >= n back into the valid range [0, n-1]
• (j + n) % n maps negative indices to their positive equivalents (e.g., -1 becomes n-1)

After processing all positions, we return the ans array containing the decrypted values.

Example Walkthrough

Let's walk through a small example with code = [2, 4, 9, 3] and k = -2.

Since k = -2 (negative), we need to replace each element with the sum of the previous 2 elements.

Initial Setup:

• n = 4 (length of array)
• Create ans = [0, 0, 0, 0] to store results

Processing each position:

Position i = 0:

• Need to sum previous 2 elements: positions from (0 + (-2)) = -2 to (0 - 1) = -1
• For j = -2: (-2 + 4) % 4 = 2, so we add code[2] = 9
• For j = -1: (-1 + 4) % 4 = 3, so we add code[3] = 3
• ans[0] = 9 + 3 = 12

Position i = 1:

• Need to sum previous 2 elements: positions from (1 + (-2)) = -1 to (1 - 1) = 0
• For j = -1: (-1 + 4) % 4 = 3, so we add code[3] = 3
• For j = 0: (0 + 4) % 4 = 0, so we add code[0] = 2
• ans[1] = 3 + 2 = 5

Position i = 2:

• Need to sum previous 2 elements: positions from (2 + (-2)) = 0 to (2 - 1) = 1
• For j = 0: (0 + 4) % 4 = 0, so we add code[0] = 2
• For j = 1: (1 + 4) % 4 = 1, so we add code[1] = 4
• ans[2] = 2 + 4 = 6

Position i = 3:

• Need to sum previous 2 elements: positions from (3 + (-2)) = 1 to (3 - 1) = 2
• For j = 1: (1 + 4) % 4 = 1, so we add code[1] = 4
• For j = 2: (2 + 4) % 4 = 2, so we add code[2] = 9
• ans[3] = 4 + 9 = 13

Final Result: [12, 5, 6, 13]

The circular array behavior is clearly demonstrated at position 0, where we wrap around to access elements at the end of the array (indices 2 and 3).

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n × |k|), where n is the length of the input array code and |k| is the absolute value of k.

This is because:

• The outer loop iterates through all n elements of the array
• For each element i, the inner loop runs exactly |k| times:
  • When k > 0: the loop runs from i + 1 to i + k + 1, which is k iterations
  • When k < 0: the loop runs from i + k to i, which is |k| iterations
• Each iteration of the inner loop performs a constant time operation (addition and modulo)

The space complexity is O(1) if we exclude the space used for the output array ans. The only additional space used is for the loop variables i and j, which require constant space regardless of the input size.

If we include the output array, the total space complexity would be O(n) since ans has the same length as the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Negative Indices

The Pitfall: When k < 0, developers often forget to handle negative indices properly when wrapping around the circular array. Simply using j % n for negative values of j won't work correctly in most programming languages.

For example, if i = 0 and k = -2, the range would be from -2 to -1. Using -1 % n in Python gives n-1 (which is correct), but in many other languages like Java or C++, -1 % n returns -1, causing an array index out of bounds error.

Incorrect approach:

# This might fail in other languages or cause confusion
for j in range(i + k, i):
    result[i] += code[j % n]  # Risky with negative j values

The Solution: Always add n before taking the modulo to ensure positive indices:

for j in range(i + k, i):
    result[i] += code[(j + n) % n]  # Safe for negative indices

2. Off-by-One Errors in Range Calculation

The Pitfall: Developers might incorrectly calculate the range endpoints, especially forgetting that Python's range() is exclusive of the end value.

Common mistakes:

# Mistake 1: Including current element when k > 0
for j in range(i, i + k):  # Wrong! Includes code[i]
    result[i] += code[j % n]

# Mistake 2: Wrong endpoint when k > 0
for j in range(i + 1, i + k):  # Wrong! Missing one element
    result[i] += code[j % n]

The Solution: Ensure the range correctly excludes the current element and includes exactly k elements:

# Correct: sum exactly k elements after position i
for j in range(i + 1, i + k + 1):  # i+1 to i+k inclusive
    result[i] += code[j % n]

3. Not Handling the k = 0 Case Early

The Pitfall: Forgetting to handle k = 0 as a special case can lead to unnecessary computation or incorrect logic in the main loop.

The Solution: Always check for k = 0 first and return immediately:

if k == 0:
    return [0] * n  # Early return with all zeros

4. Using the Wrong Modulo Formula

The Pitfall: Mixing up when to use j % n versus (j + n) % n can lead to incorrect results or runtime errors.

Rule of thumb:

• Use j % n when j is guaranteed to be non-negative
• Use (j + n) % n when j might be negative
• For extra safety, you can always use (j % n + n) % n which works for both positive and negative values

Universal safe approach:

def safe_mod(j, n):
    return (j % n + n) % n

# Then use it consistently:
result[i] += code[safe_mod(j, n)]