#239

Hard

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Sliding Window Maximum

Solve the "Sliding Window Maximum" problem using efficient techniques like the sliding window, deque, and priority queues.

array queue sliding window heap priority queue monotonic queue

Problem Statement

You are given an integer array nums and a sliding window of size k. As the window moves from left to right, you need to find the maximum value of each window and return the list of these maximums. Each time the window moves right by one position, you can only see the k numbers in the current window.

For example, with nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the result will be [3, 3, 5, 5, 6, 7], as these are the maximum values in the respective windows as the window slides.

Examples

Example 1

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

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

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]

Example details omitted.

Constraints

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

Solution Approach

Deque-based Approach

To efficiently solve this problem, we can use a deque (double-ended queue) to maintain the indices of the elements in the current sliding window. As we iterate through the array, we discard elements that are no longer in the window and ensure the deque contains the indices in decreasing order of their corresponding values. The front of the deque always holds the index of the maximum element in the window.

Brute Force Approach

A straightforward but inefficient approach is to iterate over every sliding window, compute the maximum value for each window, and return the results. This results in a time complexity of O(n * k), which is inefficient for large inputs.

Priority Queue Approach

Another approach is to use a priority queue (heap). As the window slides, we add new elements and remove those that are no longer in the window. This allows us to always access the maximum element efficiently, but it still has an O(n log k) time complexity due to the heap operations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The deque-based approach has a time complexity of O(n), as each element is added and removed from the deque at most once. The space complexity is O(k) due to the storage required for the deque. The brute force approach has a time complexity of O(n * k), and the priority queue approach has a time complexity of O(n log k) with O(k) space for the heap.

What Interviewers Usually Probe

The candidate can identify and utilize efficient data structures like deque and priority queues for sliding window problems.
The candidate understands the importance of optimizing time complexity for large inputs.
The candidate can evaluate trade-offs between different approaches based on performance characteristics.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the problem's constraints and attempting inefficient brute force solutions for large inputs.
Overcomplicating the solution with unnecessary data structures or algorithms.
Failing to maintain the sliding window correctly, causing incorrect results when the window moves.

Follow-up variants

Find the minimum value in the sliding window instead of the maximum.
Modify the problem to handle non-integer values, such as floating-point numbers or strings.
Change the window size k dynamically while the array is being processed.

FAQ

What is the optimal approach for solving Sliding Window Maximum?

The optimal approach is to use a deque to maintain the indices of the elements in the current window. This allows efficient access to the maximum value for each window.

What is the time complexity of the brute force solution for this problem?

The brute force solution has a time complexity of O(n * k), where n is the length of the array and k is the window size.

Can a priority queue be used for this problem?

Yes, a priority queue (heap) can be used to solve the problem, but it results in a time complexity of O(n log k).

What is the sliding window pattern in this problem?

The sliding window pattern refers to maintaining a window of size k and updating the window's state as it moves from left to right over the array.

How does GhostInterview help with solving Sliding Window Maximum?

GhostInterview guides you through understanding efficient approaches, such as using deques and priority queues, and helps avoid common mistakes while maintaining the sliding window state.

terminal

Solution

Solution 1: Priority Queue (Max-Heap)

We can use a priority queue (max-heap) to maintain the maximum value in the sliding window.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = [(-v, i) for i, v in enumerate(nums[: k - 1])]
        heapify(q)
        ans = []
        for i in range(k - 1, len(nums)):
            heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heappop(q)
            ans.append(-q[0][0])
        return ans

Solution 2: Monotonic Queue

To find the maximum value in a sliding window, a common method is to use a monotonic queue.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = [(-v, i) for i, v in enumerate(nums[: k - 1])]
        heapify(q)
        ans = []
        for i in range(k - 1, len(nums)):
            heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heappop(q)
            ans.append(-q[0][0])
        return ans

Continue Practicing

#862 shortest subarray with sum at least k #1425 constrained subsequence sum #1438 longest continuous subarray with absolute diff less than or equal to limit