Sliding Window Maximum - Java Solution

1. Introduction

This blog post explores the solution to a classic problem in array processing using the sliding window technique: finding the maximum element in every contiguous subarray of a specified size k in a given array.

Problem

Given an array of integers a and an integer k, find the maximum for each and every contiguous subarray of size k.

Example:

Input: a[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, k = 3

Output: 3 3 4 5 5 5 6

2. Solution Steps

1. Use a Deque (double-ended queue) to keep track of the indices of potential maximum elements for each window.

2. For each element in the array, remove elements from the back of the deque if they are less than or equal to the current element.

3. Add the index of the current element to the back of the deque.

4. Ensure that the deque only contains elements from the current window.

5. The front of the deque will always be the index of the maximum element for the current window.

6. Slide the window and repeat these steps.

3. Code Program

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 1, 4, 5, 2, 3, 6};
        printMaxOfSubarrays(a, 3);
    }

    // Method to print the maximum of all subarrays of size k
    public static void printMaxOfSubarrays(int[] a, int k) {
        Deque<Integer> deque = new LinkedList<>();

        // Process first k elements
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && a[deque.peekLast()] <= a[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
        }

        for (int i = k; i < a.length; i++) {
            System.out.print(a[deque.peek()] + " ");

            // Remove elements out of the current window
            while (!deque.isEmpty() && deque.peek() <= i - k) {
                deque.removeFirst();
            }

            // Remove all elements smaller than the currently being added element
            while (!deque.isEmpty() && a[deque.peekLast()] <= a[i]) {
                deque.removeLast();
            }

            // Add current element to the deque
            deque.addLast(i);
        }

        // Print the maximum element of the last window
        System.out.println(a[deque.peek()]);
    }
}

Output:

3 3 4 5 5 5 6

Explanation:

The printMaxOfSubarrays method uses a deque to efficiently track the maximum element in each sliding window of size k. The method ensures that the deque always contains indices of elements that are potential candidates for the maximum in the current window. 

For the input array [1, 2, 3, 1, 4, 5, 2, 3, 6] and k = 3, it outputs the maximum elements of each subarray of size 3, which are 3, 3, 4, 5, 5, 5, and 6 respectively.