Sliding Window Maximum
Given an array arr[] and an integer K, find the maximum value in every contiguous subarray of size K.
Example:
Input: arr[] = {1, 2, 3, 1, 4, 5}, K = 3
Output: 3 3 4 5Explanation:
Maximum of 1, 2, 3 is 3
Maximum of 2, 3, 1 is 3
Maximum of 3, 1, 4 is 4
Maximum of 1, 4, 5 is 5This problem asks for the maximum element in every contiguous subarray of size K. The standard solution uses a monotonic deque to keep candidate indices in decreasing order of value, removing indices that fall out of the window and discarding smaller elements when a new value enters. This allows each window maximum to be reported in O(1) amortized time, giving an overall O(n) solution instead of the brute-force O(nK) approach.
END
