Problem of The Day: Defuse the Bomb

Problem Statement

Intuition

To solve the problem of decrypting the code, the first thought is to identify the relationship between the elements in the array and how they are summed based on the given value k. If k is positive, we need to sum the next k elements in a circular manner. If k is negative, we sum the previous |k| elements, also in a circular manner. If k is zero, all values in the result should simply be 0.

Approach

1. Handle Edge Cases:

   • If k == 0, the result is straightforward — a list of zeros with the same length as code.

2. Adjust k:

   • Normalize k to always work with a positive value for simplicity. Use a flag (is_forward) to determine if we are summing forward or backward.

3. Circular Indexing:

   • Use modular arithmetic (%) to handle wrapping around the array indices. This ensures the sums are performed in a circular manner.

4. Iterate Through Each Element:

   • For each element in the array, sum the k elements either forward or backward depending on the value of k.

5. Build the Result:

   • Store the computed sums for each index into the result array.

Complexity

• Time complexity:
  \(O(n \cdot k)\)
  We loop through each of the n elements in the list and, for each element, perform a summation over k elements.

• Space complexity:
  \(O(n)\)
  The result array requires O(n) space, and no additional significant memory is used.

Code

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        N = len(code)  # Length of the input array
        if k == 0:  # Special case: if k is 0, return an array of zeros
            return [0] * N

        is_forward = (k > 0)  # Determine if we are summing forward or backward
        k = abs(k)  # Work with the absolute value of k

        res = code[:]  # Initialize the result array with the same size as the input
        for i in range(N):  # Iterate through each element in the input array
            res[i] = 0  # Initialize the sum for the current index
            for j in range(1, k + 1):  # Sum the next k elements
                if is_forward:
                    res[i] += code[(i + j) % N]  # Forward summation with circular indexing
                else:
                    res[i] += code[(i - j) % N]  # Backward summation with circular indexing
        return res  # Return the final result array

Editorial

Brute Force

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

• time: O(n*k)
• space: O(n)

Approach 2: Sliding Window

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        result = [0 for _ in range(len(code))]
        if k == 0:
            return result
        # Define the initial window and initial sum
        start, end, window_sum = 1, k, 0
        # If k < 0, the starting point will be end of the array.
        if k < 0:
            start = len(code) - abs(k)
            end = len(code) - 1
        for i in range(start, end + 1):
            window_sum += code[i]
        # Scan through the code array as i moving to the right, update the window sum.
        for i in range(len(code)):
            result[i] = window_sum
            window_sum -= code[start % len(code)]
            window_sum += code[(end + 1) % len(code)]
            start += 1
            end += 1
        return result

• time: O(n)
• space: O(n)