Sliding Window GCD

Problem Description

You are given an array of integers nums of length N. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return an array of length N - k + 1 representing the GCD of each subarray of length k from left to right.

Solution Approach

The solution to this problem involves implementing a special queue data structure using two stacks. This special queue allows the push, pop, and GCD operations in O(1) amortized time complexity. The implementation of this queue is based on the combination of two existing techniques: implementing a queue using stacks and implementing a stack that stores GCD values. By using this special queue, we can efficiently calculate the GCD for each sliding window in O(N) time complexity.

This technique is useful to understand the implementation of our queue data structure. You can refer to this resource for further details.

Here's the solution in Python, you can access the code in this playground link.

Test Cases

Test Case:

Input:
nums = [5, 15, 30, 12, 8, 18, 9]
k = 3

Output:
[5, 3, 2, 2, 1]

Explanation:
Window -> GCD
[5 15 30] 12 8 18 9 -> 5
5 [15 30 12] 8 18 9 -> 3
5 15 [30 12 8] 18 9 -> 2
5 15 30 [12 8 18] 9 -> 2
5 15 30 12 [8 18 9] -> 1

Tags

Queue, Stack, Sliding Window