Jobs

Interviews

Discussions

Sliding Window Maximum

Hard

Nuro

0 views

Topics:

ArraysSliding Windows

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

Sliding Window Maximum

Hard

Nuro

0 views

Topics:

ArraysSliding Windows

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

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 is the range of values for the integers in the input array `nums`?
Can `k` be larger than the size of `nums`, and if so, what should the output be?
Can the input array `nums` be empty or null? If so, what should be returned?
Are there any memory constraints or limitations on the size of the output array?
What should be returned if `k` is zero or negative?

Brute Force Solution

Approach

Imagine you're looking through a long line of numbers, and you want to find the biggest number within each chunk of a certain size. The brute force method simply checks every possible chunk, one by one. It's like sliding a window along the numbers and, for each window position, exhaustively scanning all the numbers within that window.

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

First, take the very first group of numbers with the correct size.
Look at each number within that group and find the largest one.
Write down that largest number as the maximum for that group.
Now, slide the group over by one number.
Again, look at each number within this new group and find the largest one.
Write down that largest number as the maximum for this new group.
Keep sliding the group over, one number at a time, and repeating the process of finding the largest number within each group, until you have covered all the numbers in the line.

Code Implementation

def sliding_window_maximum_brute_force(numbers, window_size):
    maximums = []
    number_of_elements = len(numbers)

    # Iterate through the array, considering each possible starting position for the window
    for i in range(number_of_elements - window_size + 1):
        window_maximum = numbers[i]

        # Iterate through the current window to find the maximum element
        for j in range(1, window_size):
            if numbers[i + j] > window_maximum:
                window_maximum = numbers[i + j]

        # Append the maximum value of the current window to the result
        maximums.append(window_maximum)

    return maximums

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates through the array of n elements using a sliding window of size k. For each of the n-k+1 possible windows, we iterate through the k elements within that window to find the maximum. Therefore, the total number of operations is approximately (n-k+1)*k. In the worst-case scenario, where k is a constant, the complexity is O(n*k).

Space Complexity

O(1) – The provided plain English explanation describes a brute-force approach that iterates through the input array and finds the maximum within each window by repeatedly scanning the numbers within that window. It does not explicitly mention the use of any auxiliary data structures like lists or hashmaps to store intermediate results. Therefore, only a few variables are likely used to keep track of the window's start and end indices and the current maximum value within the window. Since the space needed for these variables remains constant regardless of the input size N, the space complexity is O(1).

Optimal Solution

Approach

The best way to find the maximum value within a moving window is to avoid recalculating everything each time the window shifts. We'll use a special container to keep track of potentially maximum values within the current window, smartly updating it as the window slides.

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

Imagine a special container that only holds numbers that could possibly be the biggest within the current window.
As the window moves, we examine the new number coming in.
Before adding the new number to the container, we kick out any smaller numbers already in the container because they can never be the maximum in future windows.
We also remove numbers from the front of the container if they fall outside of the current window's range.
The biggest number in the current window is always at the front of this special container, so we can easily find it.
By using this smart container, we only compare numbers when necessary, avoiding redundant checks.

Code Implementation

from collections import deque

def sliding_window_maximum(numbers, window_size):
    if not numbers:
        return []

    result = []
    deque_of_indices = deque()

    for index in range(len(numbers)):
        # Remove indices that are out of the current window
        while deque_of_indices and deque_of_indices[0] <= index - window_size:
            deque_of_indices.popleft()

        # Remove indices of smaller elements from the back
        # The queue maintains a decreasing order.
        while deque_of_indices and numbers[deque_of_indices[-1]] < numbers[index]:
            deque_of_indices.pop()

        deque_of_indices.append(index)

        # Add the maximum element to the result if the window has formed.
        if index >= window_size - 1:
            # The leftmost element is always the maximum
            result.append(numbers[deque_of_indices[0]])

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input array of size n once. While iterating, we use a double-ended queue (deque) to maintain a decreasing order of elements within the sliding window. Each element is added to the deque and removed from the deque at most once. Therefore, the operations within the loop, such as adding and removing elements from the deque, take amortized constant time. Thus the overall time complexity is O(n).

Space Complexity

O(k) – The algorithm uses a special container, which, in the worst-case scenario, could hold all the elements within a single window. The size of this window is denoted by 'k'. Therefore, the auxiliary space is proportional to the window size, k. In the best case, the container would store fewer elements than k. Thus, the space complexity can be expressed as O(k), where k represents the window size.

Edge Cases

Case	How to Handle
Empty input array	Return an empty array since there are no elements to process.
k is 0	Return an empty array as a window of size 0 is invalid.
k is 1	The maximum of each window is simply the element itself, return the original array.
k is greater than the array length	Return an array containing only the maximum element of the entire array.
Array contains all identical elements	The maximum within each window will be the same element, which the algorithm correctly handles.
Array contains negative numbers and zeros	The algorithm should correctly identify the maximum even with negative numbers and zeros.
Large array size with small k	Using a deque optimization provides better time complexity compared to brute force approach, scaling the processing time effectively.
Array sorted in descending order	The first element will always be the maximum for each window, which the algorithm handles correctly.

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 is the range of values for the integers in the input array `nums`?
Can `k` be larger than the size of `nums`, and if so, what should the output be?
Can the input array `nums` be empty or null? If so, what should be returned?
Are there any memory constraints or limitations on the size of the output array?
What should be returned if `k` is zero or negative?

Brute Force Solution

Approach

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

First, take the very first group of numbers with the correct size.
Look at each number within that group and find the largest one.
Write down that largest number as the maximum for that group.
Now, slide the group over by one number.
Again, look at each number within this new group and find the largest one.
Write down that largest number as the maximum for this new group.
Keep sliding the group over, one number at a time, and repeating the process of finding the largest number within each group, until you have covered all the numbers in the line.

Code Implementation

def sliding_window_maximum_brute_force(numbers, window_size):
    maximums = []
    number_of_elements = len(numbers)

    # Iterate through the array, considering each possible starting position for the window
    for i in range(number_of_elements - window_size + 1):
        window_maximum = numbers[i]

        # Iterate through the current window to find the maximum element
        for j in range(1, window_size):
            if numbers[i + j] > window_maximum:
                window_maximum = numbers[i + j]

        # Append the maximum value of the current window to the result
        maximums.append(window_maximum)

    return maximums

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine a special container that only holds numbers that could possibly be the biggest within the current window.
As the window moves, we examine the new number coming in.
Before adding the new number to the container, we kick out any smaller numbers already in the container because they can never be the maximum in future windows.
We also remove numbers from the front of the container if they fall outside of the current window's range.
The biggest number in the current window is always at the front of this special container, so we can easily find it.
By using this smart container, we only compare numbers when necessary, avoiding redundant checks.

Code Implementation

from collections import deque

def sliding_window_maximum(numbers, window_size):
    if not numbers:
        return []

    result = []
    deque_of_indices = deque()

    for index in range(len(numbers)):
        # Remove indices that are out of the current window
        while deque_of_indices and deque_of_indices[0] <= index - window_size:
            deque_of_indices.popleft()

        # Remove indices of smaller elements from the back
        # The queue maintains a decreasing order.
        while deque_of_indices and numbers[deque_of_indices[-1]] < numbers[index]:
            deque_of_indices.pop()

        deque_of_indices.append(index)

        # Add the maximum element to the result if the window has formed.
        if index >= window_size - 1:
            # The leftmost element is always the maximum
            result.append(numbers[deque_of_indices[0]])

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty array since there are no elements to process.
k is 0	Return an empty array as a window of size 0 is invalid.
k is 1	The maximum of each window is simply the element itself, return the original array.
k is greater than the array length	Return an array containing only the maximum element of the entire array.
Array contains all identical elements	The maximum within each window will be the same element, which the algorithm correctly handles.
Array contains negative numbers and zeros	The algorithm should correctly identify the maximum even with negative numbers and zeros.
Large array size with small k	Using a deque optimization provides better time complexity compared to brute force approach, scaling the processing time effectively.
Array sorted in descending order	The first element will always be the maximum for each window, which the algorithm handles correctly.