{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Sliding Window Maximum – Solution & Complexity

Interview solutions
/
Sliding Window Maximum

1. Understanding the Problem

  • A window of k consecutive elements slides one step at a time across nums.
  • For each position of the window we report its maximum.
  • A length n array with window k yields n - k + 1 answers.

2. Why Naive Is Too Slow

  • Recomputing the max of every window from scratch is O(n * k).
  • For large inputs that is too slow, so we want each element processed a constant number of times.
  • The trick: maintain a structure that gives the current window's max in O(1).

3. A Monotonic Deque of Indices

  • Store indices in a deque whose corresponding values are decreasing.
  • Before adding a new index, pop smaller values from the back: they can never be the max while the newcomer is around.
  • The front of the deque is therefore always the index of the current window's maximum.
from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # indices, values decreasing
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        return result

4. Evicting Indices That Left the Window

  • The front index is stale once it falls outside [i - k + 1, i].
  • Pop it from the front when dq[0] <= i - k.
  • Once we have seen at least k elements (i >= k - 1), record nums[dq[0]].
from collections import deque

def max_sliding_window(nums, k):
    dq = deque()
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

5. Complexity

  • Time: O(n) since every index is added and removed from the deque at most once.
  • Space: O(k) for the deque plus O(n) for the output.

FAQ

See also:

Practice Sliding Window Maximum online (run code in the browser)Best Time to Buy and Sell Stock solution (easy)Binary Search solution (easy)Coin Change solution (medium)Container With Most Water solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?