239. Sliding Window Maximum

Given an array 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], and 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

Solution

Approach 1: O(n*k) - Brute force.

Approach 2: O(n) - keep a monotonously decreasing deque with increasing freshness -- new items get appended to the right, and outdated items get kicked out from the left.

Code (Python)

Approach 2:

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # Optimization: to save space we could have stored only the indices instead of (value, index) pairs.
        result = []
        window = deque()        
        for i in range(len(nums)):
            # append new item
            while window and window[-1][0] <= nums[i]:
                window.pop()
            window.append((nums[i], i))
            # throw away outdated items
            while window[0][1] <= i - k:
                window.popleft()
            # append max to result after forming the first window
            if i >= k - 1:
                result.append(window[0][0])
        
        return result

Code (C++)

Approach 1:

// O(n*k).
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        if (k <= 0)
            return res;
        for (int i = 0; i <= nums.size()-k; ++i)
        {
            int max = nums[i];
            for (int j = i+1; j < i + k; ++j)
            {
                if (nums[j] > max)
                    max = nums[j];
            }
            res.push_back(max);
        }
        return res;
    }
};

Approach 2:

// O(n).
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        vector<int> buf;
        int head = 0;
        for (int tail = 0; tail < nums.size(); ++tail)
        {
            while (!buf.empty() && buf.back() < nums[tail])
                buf.pop_back();
            buf.push_back(nums[tail]);
            if (tail - head + 1 == k)
            {
                res.push_back(buf.front());
                if (nums[head] == buf.front())
                    buf.erase(buf.begin());
                head++;
            }
        }
        return res;
    }
};
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> buf;
        int head = 0;
        for (int tail = 0; tail < nums.size(); ++tail)
        {
            while (!buf.empty() && buf.back() < nums[tail])
                buf.pop_back();
            buf.push_back(nums[tail]);
            if (tail - head + 1 == k)
            {
                res.push_back(buf.front());
                if (nums[head] == buf.front())
                    buf.pop_front();
                head++;
            }
        }
        return res;
    }
};