Sliding Window: 239. Sliding Window Maximum

Leetcode #: 239
Name: Sliding Window Maximum
Difficulty: Hard
Url: https://leetcode.com/problems/sliding-window-maximum/

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

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

Constraints

• 1 <= nums.length <= 105
• 104 <= nums[i] <= 104
• 1 <= k <= nums.length

Approach

Brute Force: O(k * (n — k))

We can simply take the maximum of each sliding window of size k as we shift it by 1 until we scan the given array from left to right. The time complexity of this would be the size of the sliding window (k) * the number of sliding windows we are going to have (n — k).

Monotonically Decreasing Queue: O(n)

If we have a sliding window and we see a value that is greater than previous values in our window, then we can eliminate those previous values from our window.

Code

Python | Time: O(n) | Space: O(n) | n = total number of integers in array nums

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub