BL
U

105. Sliding Window Maximum Using Deque

Med.

Problem Description

Given an array of NN integers and a sliding window of size KK moving from left to right, return the maximum element in each window in O(N)O(N) time using a monotonic deque.

Input Format

  • •Line 1: Two space-separated integers NN and KK (1≤K≤N≤1051 \le K \le N \le 10^5).
  • •Line 2: NN space-separated integers A1,…,ANA_1, \dots, A_N.

Output Format

Print N−K+1N - K + 1 space-separated integers representing the maximum for each window.

Example 1:
Input:
8 3
1 3 -1 -3 5 3 6 7
Output:
3 3 5 5 6 7
Explanation: Max for each window of size 3.
Example 2:
Input:
1 1
1
Output:
1
Explanation: Single element window.
Example 3:
Input:
4 2
4 3 2 1
Output:
4 3 2
Explanation: Decreasing array window maximums.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online