Jobs

Interviews

Discussions

Sliding Window Maximum

Hard

Asked by:

+25

More companies

414 views

Topics:

ArraysSliding WindowsStacks

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

Try coding it in LeetCode

Sliding Window Maximum

Hard

Asked by:

+19

More companies

414 views

Topics:

ArraysSliding WindowsStacks

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if the input array `nums` is empty or if `k` is larger than the size of the array?
Can the integers in the `nums` array be negative or zero?
What are the constraints on the size of the input array `nums` and the window size `k`? For instance, could `k` be 1 or equal to the length of the entire array?
Are duplicate numbers allowed within the input array, and if so, how might they appear within a single window?
Is it guaranteed that `k` will always be a positive integer?

Brute Force Solution

Approach

Imagine you have a list of numbers and a special magnifying glass that can only look at a small, fixed number of them at a time. The brute force approach is to slide this magnifying glass over the entire list, one number at a time, and for each position, we meticulously find the biggest number visible inside the glass.

Here's how the algorithm would work step-by-step:

First, position your magnifying glass over the very first group of numbers in the list.
Look at all the numbers you can see inside the glass and find the largest one among them.
Write down this largest number. This is the first result.
Now, slide the magnifying glass one spot to the right so it covers a new group of numbers.
Again, look at all the numbers currently visible inside the glass and find the biggest one.
Write down this new largest number. This is your next result.
Continue this process of sliding the glass one spot to the right and finding the biggest number inside it each time.
Keep doing this until your magnifying glass reaches the very end of the list of numbers.
The list of all the largest numbers you wrote down is your final answer.

Code Implementation

def sliding_window_maximum_brute_force(numbers_list, window_size):
    maximums_in_windows = []
    number_of_windows = len(numbers_list) - window_size + 1

    # Iterate through all possible starting positions for the sliding window.
    for window_start_index in range(number_of_windows):
        window_end_index = window_start_index + window_size
        current_window = numbers_list[window_start_index:window_end_index]

        # For each window, we must find the maximum value within that specific slice of the list.
        current_maximum_value = current_window[0]
        for number_in_window in current_window:
            if number_in_window > current_maximum_value:
                current_maximum_value = number_in_window
        
        # After finding the max for the current window, add it to our list of results.
        maximums_in_windows.append(current_maximum_value)

    return maximums_in_windows

Big(O) Analysis

Time Complexity

O(n * k) – The overall process involves iterating through the list of numbers to position the start of the window. There are approximately n - k + 1 such positions, where n is the total number of elements and k is the size of the window. For each of these positions, we must scan all k elements inside the current window to find the maximum value. This results in a total number of operations proportional to (n - k + 1) * k, which simplifies to O(n * k) because k is a variable that can approach n.

Space Complexity

O(1) – The brute force approach described only requires a few variables to store the current maximum value for each window and the index for the sliding position. The core operation is iterating through a sub-portion of the original input array to find the maximum, which doesn't require any auxiliary data structures that scale with the input size N. Therefore, the extra space used is constant.

Optimal Solution

Approach

The core idea is to cleverly keep track of potential candidates for the maximum value in a special, ordered list. Instead of re-scanning every number in the window, we maintain a shortlist of the best numbers we've seen recently, which lets us find the maximum for each new window almost instantly.

Here's how the algorithm would work step-by-step:

First, look at the initial group of numbers that form the very first window.
From this group, create a special list of candidates for the maximum. The key is to only keep useful candidates: if you see a new number that's bigger than an existing candidate, the smaller one is no longer useful, so you can discard it.
The biggest number in your special candidate list will always be at the front. Record this as the answer for the first window.
Now, slide the window one step to the right. This means you add one new number and drop one old number.
Before adding the new number to your candidate list, remove any existing candidates from the back that are smaller than the new number, since they can no longer be the maximum.
Also, check if the number at the front of your candidate list is the one that just fell out of the window. If it is, remove it because it's no longer in view.
After these adjustments, the number at the front of your candidate list is the maximum for the current window. Record it.
Repeat this process of sliding, updating your candidate list, and recording the front-runner until the window has passed over all the numbers.

Code Implementation

from collections import deque

def sliding_window_maximum(numbers_list, window_size):
    max_values_for_each_window = []
    candidate_indices_deque = deque()

    start_of_window = 0
    for end_of_window in range(len(numbers_list)):
        # Remove smaller numbers from the back as they can no longer be the maximum.
        while candidate_indices_deque and numbers_list[candidate_indices_deque[-1]] < numbers_list[end_of_window]:
            candidate_indices_deque.pop()
        
        candidate_indices_deque.append(end_of_window)

        # Remove the leftmost element if it's out of the current window's bounds.
        if start_of_window > candidate_indices_deque[0]:
            candidate_indices_deque.popleft()
        
        # The deque's front is the max for the current window once it's fully formed.
        if (end_of_window + 1) >= window_size:
            max_values_for_each_window.append(numbers_list[candidate_indices_deque[0]])
            start_of_window += 1
            
    return max_values_for_each_window

Big(O) Analysis

Time Complexity

O(n) – The time complexity is O(n) where n is the number of elements in the input array. Although there is an inner loop-like process to maintain the candidate list, each element from the input array is added to and removed from this list at most once over the entire algorithm. Therefore, the total number of operations for managing the candidate list is proportional to n. Since we iterate through the input array a single time, the total work is approximately n + n, which simplifies to O(n).

Space Complexity

O(k) – The primary auxiliary space is used by the 'special list of candidates' described in the explanation. This list stores indices of elements from the input array, and its size is determined by the window size, k. In the worst-case scenario, where the elements in a window are in decreasing order, this list could hold up to k indices. Therefore, the space complexity is proportional to the window size, k, where N is the total number of elements in the input.

Edge Cases

Case	How to Handle
Empty input array	The function should return an empty array as no windows can be formed.
Window size k is larger than the array size	Return an empty array because a full window of size k can never be formed.
Window size k is 1	The maximum of each window is just the element itself, so the original array should be returned.
Array contains all identical elements	The maximum for every window will be the same, so the result array should contain that value repeated for each window.
Array contains negative numbers, zeros, and positive numbers	The comparison logic must correctly handle the full range of integer values to find the true maximum in each window.
Window size k is equal to the array size	There is only one window, so the result should be a single-element array containing the maximum of the entire input array.
Very large input array (e.g., 10^5 elements)	A solution using a deque or a similar O(n) approach is required to avoid a timeout that would occur with a naive O(n*k) solution.
Array elements are in strictly decreasing order	An efficient deque-based solution will correctly identify the first element of each window as its maximum.

Empty input array

How to Handle:

The function should return an empty array as no windows can be formed.

Window size k is larger than the array size

How to Handle:

Return an empty array because a full window of size k can never be formed.

Window size k is 1

How to Handle:

The maximum of each window is just the element itself, so the original array should be returned.

Array contains all identical elements

How to Handle:

The maximum for every window will be the same, so the result array should contain that value repeated for each window.

Array contains negative numbers, zeros, and positive numbers

How to Handle:

The comparison logic must correctly handle the full range of integer values to find the true maximum in each window.

Window size k is equal to the array size

How to Handle:

There is only one window, so the result should be a single-element array containing the maximum of the entire input array.

Very large input array (e.g., 10^5 elements)

How to Handle:

A solution using a deque or a similar O(n) approach is required to avoid a timeout that would occur with a naive O(n*k) solution.

Array elements are in strictly decreasing order

How to Handle:

An efficient deque-based solution will correctly identify the first element of each window as its maximum.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if the input array `nums` is empty or if `k` is larger than the size of the array?
Can the integers in the `nums` array be negative or zero?
What are the constraints on the size of the input array `nums` and the window size `k`? For instance, could `k` be 1 or equal to the length of the entire array?
Are duplicate numbers allowed within the input array, and if so, how might they appear within a single window?
Is it guaranteed that `k` will always be a positive integer?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, position your magnifying glass over the very first group of numbers in the list.
Look at all the numbers you can see inside the glass and find the largest one among them.
Write down this largest number. This is the first result.
Now, slide the magnifying glass one spot to the right so it covers a new group of numbers.
Again, look at all the numbers currently visible inside the glass and find the biggest one.
Write down this new largest number. This is your next result.
Continue this process of sliding the glass one spot to the right and finding the biggest number inside it each time.
Keep doing this until your magnifying glass reaches the very end of the list of numbers.
The list of all the largest numbers you wrote down is your final answer.

Code Implementation

def sliding_window_maximum_brute_force(numbers_list, window_size):
    maximums_in_windows = []
    number_of_windows = len(numbers_list) - window_size + 1

    # Iterate through all possible starting positions for the sliding window.
    for window_start_index in range(number_of_windows):
        window_end_index = window_start_index + window_size
        current_window = numbers_list[window_start_index:window_end_index]

        # For each window, we must find the maximum value within that specific slice of the list.
        current_maximum_value = current_window[0]
        for number_in_window in current_window:
            if number_in_window > current_maximum_value:
                current_maximum_value = number_in_window
        
        # After finding the max for the current window, add it to our list of results.
        maximums_in_windows.append(current_maximum_value)

    return maximums_in_windows

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, look at the initial group of numbers that form the very first window.
From this group, create a special list of candidates for the maximum. The key is to only keep useful candidates: if you see a new number that's bigger than an existing candidate, the smaller one is no longer useful, so you can discard it.
The biggest number in your special candidate list will always be at the front. Record this as the answer for the first window.
Now, slide the window one step to the right. This means you add one new number and drop one old number.
Before adding the new number to your candidate list, remove any existing candidates from the back that are smaller than the new number, since they can no longer be the maximum.
Also, check if the number at the front of your candidate list is the one that just fell out of the window. If it is, remove it because it's no longer in view.
After these adjustments, the number at the front of your candidate list is the maximum for the current window. Record it.
Repeat this process of sliding, updating your candidate list, and recording the front-runner until the window has passed over all the numbers.

Code Implementation

from collections import deque

def sliding_window_maximum(numbers_list, window_size):
    max_values_for_each_window = []
    candidate_indices_deque = deque()

    start_of_window = 0
    for end_of_window in range(len(numbers_list)):
        # Remove smaller numbers from the back as they can no longer be the maximum.
        while candidate_indices_deque and numbers_list[candidate_indices_deque[-1]] < numbers_list[end_of_window]:
            candidate_indices_deque.pop()
        
        candidate_indices_deque.append(end_of_window)

        # Remove the leftmost element if it's out of the current window's bounds.
        if start_of_window > candidate_indices_deque[0]:
            candidate_indices_deque.popleft()
        
        # The deque's front is the max for the current window once it's fully formed.
        if (end_of_window + 1) >= window_size:
            max_values_for_each_window.append(numbers_list[candidate_indices_deque[0]])
            start_of_window += 1
            
    return max_values_for_each_window

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	The function should return an empty array as no windows can be formed.
Window size k is larger than the array size	Return an empty array because a full window of size k can never be formed.
Window size k is 1	The maximum of each window is just the element itself, so the original array should be returned.
Array contains all identical elements	The maximum for every window will be the same, so the result array should contain that value repeated for each window.
Array contains negative numbers, zeros, and positive numbers	The comparison logic must correctly handle the full range of integer values to find the true maximum in each window.
Window size k is equal to the array size	There is only one window, so the result should be a single-element array containing the maximum of the entire input array.
Very large input array (e.g., 10^5 elements)	A solution using a deque or a similar O(n) approach is required to avoid a timeout that would occur with a naive O(n*k) solution.
Array elements are in strictly decreasing order	An efficient deque-based solution will correctly identify the first element of each window as its maximum.

Empty input array

How to Handle:

The function should return an empty array as no windows can be formed.

Window size k is larger than the array size

How to Handle:

Return an empty array because a full window of size k can never be formed.

Window size k is 1

How to Handle:

The maximum of each window is just the element itself, so the original array should be returned.

Array contains all identical elements

How to Handle:

The maximum for every window will be the same, so the result array should contain that value repeated for each window.

Array contains negative numbers, zeros, and positive numbers

How to Handle:

The comparison logic must correctly handle the full range of integer values to find the true maximum in each window.

Window size k is equal to the array size

How to Handle:

There is only one window, so the result should be a single-element array containing the maximum of the entire input array.

Very large input array (e.g., 10^5 elements)

How to Handle:

A solution using a deque or a similar O(n) approach is required to avoid a timeout that would occur with a naive O(n*k) solution.

Array elements are in strictly decreasing order

How to Handle:

An efficient deque-based solution will correctly identify the first element of each window as its maximum.