Sliding Window Maximum

Sliding Window Maximum is a standard coding interview problem commonly featured on platforms like LeetCode (#239) and discussed in LinkedIn interview prep contexts with tags like Array, Queue, Sliding Window, Heap, and Monotonic Queue.[1][2][3]

Problem Statement

You are given an integer array nums and an integer k. A sliding window of size k moves from the left to the right of the array. For each position of the window, return the maximum value within that window. The output is an array of these maximum values for each valid window position.[2][3][7][1]

Examples

Example 1

Input: nums = [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[3][2]

Example 2

Input: nums = [1,3,2,5,8,7], k = 3
Output: [3,5,8,8]
Explanation:

• Window [1,3,2]: max = 3
• Window [3,2,5]: max = 5
• Window [2,5,8]: max = 8
• Window [5,8,7]: max = 8[3]

Example 3 (from GeeksforGeeks variant)

Input: arr[] = [1, 2, 3, 1, 4, 5, 2, 3, 6], k = 3
Output: [3, 3, 4, 5, 5, 5, 6][7]

Constraints

• 1 ≤ nums.length ≤ 10^5
• -10^4 ≤ nums[i] ≤ 10^4
• 1 ≤ k ≤ nums.length[2]