Sliding Window Maximum Solution for Cognizant

Company: Cognizant · Difficulty: Hard · Topics: Array, Sliding Window, Monotonic Queue, Deque

Problem Statement

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Examples

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3

Output: [3,3,5,5,6,7]

Example 2:

Input: nums = [1], k = 1

Output: [1]

Approach

Use a monotonic decreasing deque to maintain the maximum element in the current window.

Time and Space Complexity

• Time Complexity: O(n) - Each element is added/removed at most once
• Space Complexity: O(k) - Deque stores at most k elements

More Cognizant coding questions