Python deque

Elevate your coding journey with Python deque—a game-changer in data management. Learn how to harness dynamic data structures and code like a pro.

'''use case for using the deque data structure in Python: solving the
 "Maximum of All Subarrays of Size K" problem.
  In this problem, you are given an array of integers and a window size k.
You need to find the maximum element in each subarray of size k as the window slides through the array.

Here's a Python code example using the deque data structure to solve this problem:'''

from collections import deque


def max_in_subarrays(arr, k):
    result = []  # To store the maximum values of each subarray
    dq = deque()  # To store indices of elements within the current window

    for i in range(len(arr)):
        # Remove indices of elements that are out of the current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove indices of elements that are smaller than the current element
        while dq and arr[dq[-1]] < arr[i]:
            dq.pop()

        dq.append(i)  # Add the current element's index

        # Start adding maximum values to the result once the window is of size k
        if i >= k - 1:
            result.append(arr[dq[0]])

    return result


# Example usage
arr = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
result = max_in_subarrays(arr, k)
print(result)  # Output: [3, 3, 5, 5, 6, 7]