239. Sliding Window Maximum
Sliding Window Maximum (LeetCode 239) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Monotonic Queue for Max/Min subpattern.
How to solve Sliding Window Maximum
Sliding Window Maximum is a Monotonic Queue for Sliding Window Maximum/Minimum problem, part of Sliding Window. Master monotonic queue (deque) to find maximum or minimum in sliding windows efficiently in O(n) time.
Work towards the solution in these steps:
- How about using a data structure such as deque (double-ended queue)?
- The queue size need not be the same as the window’s size.
- Remove redundant elements and the queue should store only elements that need to be considered.
The reference solution runs in O(n) time and O(k) space.
The Sliding Window Maximum solution and editorial walks through the full approach with reference code.
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.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
- 1 <= k <= nums.length
Topics and companies
Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue.
Reported in interviews at Akuna Capital, Amazon, Apple, Bloomberg, ByteDance, Citadel, Dropbox, Facebook, Google, IBM, Microsoft, Twitter and others.
How to practise Sliding Window Maximum on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(k) space.
Open Sliding Window Maximum in the code editor, or read the Sliding Window Maximum editorial for a worked solution with its approach and complexity analysis.
Where Sliding Window Maximum sits in the DSA pattern sheet
Problems related to Sliding Window Maximum
Other problems that use the same Monotonic Queue for Max/Min and Sliding Window techniques:
- Jump Game VI — Medium, same subpattern
- Shortest Subarray with Sum at Least K — Hard, same subpattern
- Calculate Compressed Mean — Easy, same pattern
- Contains Duplicate II — Easy, same pattern
- Continuous Subarrays — Medium, same pattern
- Find All Anagrams in a String — Medium, same pattern
Sliding Window Maximum FAQ
What is the LeetCode number of Sliding Window Maximum?
Sliding Window Maximum is LeetCode problem 239, rated Hard.
What pattern is used to solve Sliding Window Maximum?
Sliding Window Maximum is a Monotonic Queue for Sliding Window Maximum/Minimum problem. It belongs to the Sliding Window pattern, in the Monotonic Queue for Max/Min subpattern.
What is the time complexity of Sliding Window Maximum?
The reference solution runs in O(n) time and O(k) space.
Which companies ask Sliding Window Maximum?
Sliding Window Maximum has been reported in interviews at Akuna Capital, Amazon, Apple, Bloomberg, ByteDance, Citadel, Dropbox, Facebook, Google, IBM, Microsoft, Twitter and others.