Given an array and a window size, find the maximum element in each sliding window.

Problem :

Given an array and a window size, find the maximum element in each sliding window.
Topic: Deque, Heap

Problem Statement:

You are given an array of integers and a window size k. Your task is to find the maximum element in each sliding window of size k as the window slides from left to right across the array.

Example:

Input:

• Array: [1, 3, -1, -3, 5, 3, 6, 7]
• Window Size (k): 3

Output:

• Maximum in each window: [3, 3, 5, 5, 6, 7]

Thought Process:

1. Sliding Window Concept:
   We need to move a window of size k across the array and find the maximum in each window. The challenge is to efficiently calculate the maximum without recalculating it for overlapping elements. Brute-force recalculation would result in O(n*k), which can be optimized to O(n) with Deque or Heap.
2. Deque (Double-Ended Queue) Approach:
   A Deque is ideal because we can maintain a sliding window of indices and efficiently keep track of the maximum element in O(1) time by performing these operations:

• Maintain decreasing order in the Deque: As we iterate over the array, we store the indices of the elements in the Deque. We remove elements from the Deque if they are smaller than the current element because they will never be useful as they would not be the maximum in any future windows.
• Remove out-of-bound indices: If the index at the front of the Deque is out of the current window (older than the current window’s left boundary), remove it.
• The front of the Deque holds the index of the maximum element for the current window. This allows us to find the maximum element in O(1) for each window after the initial setup.

Detailed Step-by-Step Solution:

Step 1: Define the Problem and Plan

1. Input:

• An array of integers nums[] and an integer k (window size).

1. Output:

• A list of maximum elements from each window of size k.

Step 2: Deque Solution in Detail

1. Initialize a deque dq to store indices of elements in the current window.
2. Traverse through each element in the array:

• Remove out-of-bound indices: If the front of the deque is outside the current window (i.e., index is less than i - k + 1), remove it from the deque.
• Maintain decreasing order: If the current element is greater than the elements represented by the indices in the deque, remove those indices because the current element will dominate them in future windows.
• Add the current element’s index to the deque.
• Store the maximum for the current window: If the window is at least size k, append the element at the front of the deque (the maximum) to the result list.

1. Return the result list.

Code Explanation

from collections import deque

def sliding_window_max(nums, k):
    # Result list to store the maximums
    result = []
    # Deque to store indices of array elements
    dq = deque()

    # Traverse through the entire array
    for i in range(len(nums)):
        # Remove indices of elements that are out of the current window
        if dq and dq[0] < i - k + 1:
            dq.popleft()

        # Maintain decreasing order in the deque: Remove elements smaller than the current element
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

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

        # Store the maximum element of the current window (when i >= k-1)
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Example
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(sliding_window_max(nums, k))  # Output: [3, 3, 5, 5, 6, 7]

Step-by-Step Code Walkthrough:

1. Import Required Library:

• We use the deque from the collections module for efficient addition and removal from both ends.

1. Initialize Variables:

• result[]: To store the maximum values for each sliding window.
• dq: A deque to store indices of the elements. It helps us track the maximums within the window.

1. Loop Over Array:

• For each index i, perform the following checks:
  • Remove Out-of-Bounds Elements: If the index at the front of the deque is outside the current window (older than i - k + 1), remove it.
  • Maintain Decreasing Order: While the deque is not empty, and the current element nums[i] is greater than the elements pointed to by the indices in the deque, pop the indices from the deque. The idea is to discard elements that won’t be useful for future maximums.
  • Append the Current Element’s Index: Add the index i to the deque.
  • Store the Maximum for the Window: Once we reach the window size k (i >= k-1), append the maximum for the current window (the element at the front of the deque) to the result list.

1. Return the Result:

• After processing all elements, return the result list which contains the maximums for each window.

Time Complexity:

• O(n): We traverse the array once, and each element is added and removed from the deque at most once.
• Space Complexity:
• O(k): The deque stores at most k elements (indices), as it’s bounded by the window size.

Output:

For the input nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the output is:

[3, 3, 5, 5, 6, 7]

Final Thoughts:

The deque solution provides an optimal O(n) solution by maintaining only the relevant elements in the window. Each operation (insert, remove) is done in constant time due to the efficient operations of the deque.

Share on Facebook

Post on X

Follow us

Save