Leetcode 239: Sliding Window Maximum

The original question can be found here.

The question is asking to find the maximum number inside each sliding window(subarray).

Brute Force

Go through each subarray and find the maximum value.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        for start in range (0, len(nums) - k + 1):
            max_num = -math.inf
            for i in range(start, start + k):
                max_num = max(max_num, nums[i])
            ans.append(max_num)
        return ans

The time complexity is O(n*k), where n is the size of nums array. Space complexity is O(1).

Heap

Definitely interviewer won’t satisfy if we only provide the brute force solution. How can we do better? Since we have to iterate through the array at least once, so we can’t beat O(n). Can we optimize the solution to achieve the O(n) time complexity?

The hard part is how we track the numbers in a subarray while proceeding to next series of subarrays. The easist way we can think of is using a max heap. I’m using Java for this piece of code since Python does not support max heap so well.

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue(Comparator.reverseOrder());
        int[] ans = new int[nums.length - k + 1];
        int ansPosition = 0;
        for (int i = 0; i < nums.length; i++) {
            pq.add(nums[i]);
            if (pq.size() == k) {
                ans[ansPosition++] = pq.peek();
                pq.remove(nums[i - k + 1]);
            }
        }
        return ans;
    }
}

The time complexity is O(n*lg(k)), and space complexity is O(k).

Deque

To be continued…