K Sized Subarray Maximum

JavaView on GFG

Time: O(n)

Space: O(k)

Intuition

Sliding window maximum. Monotone deque maintains candidates for maximum in decreasing order.

Algorithm

1Deque of indices (decreasing values). For each element: remove indices out of window from front. Remove elements smaller than current from back. Add current index.
2Front of deque is max of current window.

Common Pitfalls

•Remove from front if index out of window range. Deque stores indices, not values.

K Sized Subarray Maximum.java

Java

// Approach: Monotonic deque. Maintain decreasing deque of indices; front is max of current window.
// Time: O(n) Space: O(k)
import java.util.*;

class Solution {
    // Function to find maximum of each subarray of size k.
    public ArrayList<Integer> max_of_subarrays(int k, int arr[]) {
        ArrayList<Integer> result = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()])
                deque.removeLast();

            deque.addLast(i);
        }

        for (int i = k; i < arr.length; i++) {
            result.add(arr[deque.peek()]);

            while (!deque.isEmpty() && deque.peek() <= i - k)
                deque.removeFirst();

            while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()])
                deque.removeLast();

            deque.addLast(i);
        }

        result.add(arr[deque.peek()]);

        return result;
    }
}

Was this solution helpful?