Return the Maximum of Every Sliding Window

Question

The question asks the candidate to implement a function that returns the maximum value from each sliding window of a specified size within an array.

Codemia · Accepted Answer

To solve the problem of finding the maximum in every sliding window of size `k`, we can use a deque (double-ended queue) to keep track of indices of elements in the current window. This allows us to efficiently retrieve the maximum value as we slide the window across the array.

1. Initialize a deque to store indices of array elements.  
2. Iterate through the array:  
   - Remove indices that are out of the bounds of the current window.  
   - Remove elements from the deque that are less than the current element, as they will not be needed for future windows.  
   - Add the current index to the deque.  
   - If the current index is greater than or equal to `k - 1`, append the maximum (the front of the deque) to the result list.

The time complexity of this approach is O(n) because each element is added and removed from the deque at most once. The space complexity is O(k) for the deque, where k is the size of the sliding window.

```python
from collections import deque

def max_sliding_window(nums, k):
    if not nums or k == 0:
        return []
    result = []
    dq = deque()
    for i in range(len(nums)):
        # Remove indices that are out of the current window
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        # Remove elements that are less than the current element
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        # Append the maximum for the current window
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result
```
This function will return the maximum values for each sliding window of size `k`.

Consider edge cases such as an empty array or a window size of zero. In such cases, the function should return an empty list. Additionally, if `k` is greater than the length of the array, we should handle this gracefully.

Return the Maximum of Every Sliding Window

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Amazon Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string