Maximum of all subarrays of size k

Problem Statement

Given an array and an integer K, find the maximum element in each sliding window of size K.

Example:

• Input: arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
• Output: [3, 3, 5, 5, 6, 7]
• Explanation:
  • Window [1, 3, -1] → max = 3
  • Window [3, -1, -3] → max = 3
  • Window [-1, -3, 5] → max = 5
  • Window [-3, 5, 3] → max = 5
  • Window [5, 3, 6] → max = 6
  • Window [3, 6, 7] → max = 7

Approach 1: Brute Force

Intuition

For each window position, iterate through all K elements to find the maximum.

Algorithm

1. For each starting position i from 0 to n-k
2. Find maximum in the window arr[i...i+k-1]
3. Add to result

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        
        for (int i = 0; i <= n - k; i++) {
            int maxVal = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                maxVal = Math.max(maxVal, nums[j]);
            }
            result[i] = maxVal;
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n * k) - For each of n-k+1 windows, we scan k elements
• Space Complexity: O(n - k + 1) - For storing results

Approach 2: Using Max-Heap

Intuition

Use a max-heap to track the maximum element. The heap stores pairs of (value, index) so we can remove elements that are outside the current window.

Algorithm

1. Initialize max-heap with first k elements
2. For each new window position:
   • Remove elements from heap top that are outside window
   • Add new element to heap
   • Record the heap top as window maximum

import java.util.PriorityQueue;
import java.util.Comparator;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        
        // Max-heap of {value, index}
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]
        );
        
        // Add first k elements
        for (int i = 0; i < k; i++) {
            maxHeap.offer(new int[]{nums[i], i});
        }
        
        result[0] = maxHeap.peek()[0];
        
        // Process remaining elements
        for (int i = k; i < n; i++) {
            // Add new element
            maxHeap.offer(new int[]{nums[i], i});
            
            // Remove elements outside window
            while (maxHeap.peek()[1] <= i - k) {
                maxHeap.poll();
            }
            
            result[i - k + 1] = maxHeap.peek()[0];
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n log n) - Each element is pushed/popped at most once, each operation is O(log n)
• Space Complexity: O(n) - Heap can contain all elements in worst case

Approach 3: Deque (Optimal)

Intuition

Use a monotonic deque that stores indices. The deque maintains elements in decreasing order of their values. The front always contains the index of the maximum element for the current window.

Algorithm

1. Process first k elements, maintaining decreasing order in deque
2. For each new element:
   • Remove indices outside window from front
   • Remove smaller elements from back (they can never be max)
   • Add current index
   • Front of deque is the maximum

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>(); // Store indices
        
        for (int i = 0; i < n; i++) {
            // Remove indices outside window
            while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            
            // Remove smaller elements
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            
            dq.offerLast(i);
            
            // Start recording results after first window
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Each element is pushed and popped at most once
• Space Complexity: O(k) - Deque stores at most k elements

Key Takeaways

1. Brute Force is intuitive but inefficient for large arrays
2. Max-Heap approach works but lazy deletion leads to O(n log n)
3. Monotonic Deque is optimal - maintains decreasing order for O(1) max access
4. Store indices in deque to easily check if element is in window
5. Elements smaller than current can be safely removed - they'll never be the max
6. This pattern applies to many sliding window problems with min/max queries
7. Also known as "Sliding Window Maximum" - a classic interview problem (LeetCode 239)