{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Sliding Window Maximum – Solution & Complexity

Interview solutions
/
Sliding Window Maximum

Solution Walkthrough

  1. Step 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. Step 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. Step 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):
        if dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

  4. Step 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. Step 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.
Learn the Sliding Window pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Sliding Window Maximum online (run code in the browser)Minimum Size Subarray Sum solution (medium)01 Matrix solution (medium)3Sum solution (medium)3Sum Closest solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?