Sliding Window Maximum - Java Solution

1. Introduction

In this post, we will explore a solution to the "Sliding Window Maximum" problem, which is a classic example of a sliding window algorithm. The task involves finding the maximum element in each window of size k as the window slides through the entire array from left to right.

Problem

Given an array of integers nums and an integer k, representing the size of the sliding window, the goal is to return an array containing the maximum element from each window as the window slides from the beginning to the end of the array.

Examples:

- Input: nums = [1,3,-1,-3,5,3,6,7], k = 3

Output: [3,3,5,5,6,7]

- Input: nums = [1], k = 1

Output: [1]

2. Solution Steps

1. Use a Deque (Double Ended Queue) to store indices of useful elements for each window.

2. Iterate through the array:

a. Remove indices that are out of the current window from the front of the Deque.

b. Remove indices from the back of the Deque if the corresponding elements are smaller than the current element.

c. Add the current index to the back of the Deque.

d. The front of the Deque will always hold the index of the maximum element for the current window.

e. Add the maximum element to the result for each window.

3. Return the resulting array of maximum elements.

3. Code Program

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

public class SlidingWindowMaximum {
    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] result = maxSlidingWindow(nums, k);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }

    // Function to find the maximum in each sliding window
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) return new int[0];
        int[] result = new int[nums.length - k + 1];
        int ri = 0;

        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            // Remove numbers out of range k
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }

            // Remove smaller numbers as they are useless
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // Add new value
            deque.offer(i);
            if (i >= k - 1) {
                result[ri++] = nums[deque.peek()];
            }
        }
        return result;
    }
}

Output:

3 3 5 5 6 7

Explanation:

1. maxSlidingWindow: This function computes the maximum element in each sliding window of size k.

2. A Deque is used to hold indices of array elements. This Deque is maintained such that its front always has the index of the current window's maximum element.

3. The algorithm iteratively checks each element of the array:

- It removes indices from the Deque that are outside the current window.

- It also removes indices of elements from the back of the Deque if those elements are less than the current element, as they cannot be the maximum for the current or future windows.

- Then, it adds the current index to the Deque.

4. For each window, the maximum value (the front of the Deque) is added to the result array.

5. The approach ensures that for each window, the maximum element is efficiently found and stored.

6. This method is optimal for such problems due to its linear time complexity and constant space usage (excluding the output array).