Defuse the Bomb

XXX. Decrypt Rotated Array

Sliding Window

Modular Arithmetic

Problem Statement:

You are given a circular array code of integers and an integer k. The goal is to modify the array such that each element becomes the sum of the next k or previous k elements, depending on whether k is positive or negative.

If k = 0, all elements of the resulting array should be 0.

Algorithm:

The solution uses a sliding window approach to efficiently calculate the sums:

1. Initialize the result array res with the same length as code. If k = 0, return the result array filled with zeros.
2. Determine the initial window range based on the value of k:
   • If k > 0, the window starts from the first index and ends at the kth index.
   • If k < 0, convert k to positive and set the window to cover the last k elements.
3. Calculate the sum of the initial window.
4. Slide the window across the array, updating the sum by adding the next element and subtracting the previous element in the window using modular arithmetic to handle the circular array.
5. Store the sum for each element in the result array.

Complexity:

Time Complexity: O(n), where n is the length of the array. Each element is processed once.
Space Complexity: O(n), for the result array.

Java Implementation:

class Solution {
    public int[] decrypt(int[] code, int k) {
        int[] res = new int[code.length]; // Result array
        if (k == 0) return res; // If k = 0, return array of zeros

        // Define the initial window and calculate its sum
        int start = 1, end = k, sum = 0;
        if (k < 0) { // If k < 0, adjust the window to the end of the array
            k = -k;
            start = code.length - k;
            end = code.length - 1;
        }

        for (int i = start; i <= end; i++) sum += code[i];

        // Slide the window and update the result array
        for (int i = 0; i < code.length; i++) {
            res[i] = sum; // Store the current window sum
            sum -= code[start++ % code.length]; // Remove the element going out of the window
            sum += code[++end % code.length]; // Add the new element coming into the window
        }

        return res;
    }
}

Explanation:

The sliding window technique efficiently calculates the sum for each element by maintaining a running sum of the current window. The modular arithmetic ensures the indices wrap around the circular array.

• Initialization: The initial window is set based on the value of k, and its sum is calculated.
• Sliding the Window: For each element, the sum is updated by adding the next element and removing the previous one, ensuring constant-time updates per iteration.
• Result Array: The updated sums are stored in the result array as the window slides across the array.