Coding Interview: How Do You Solve Sliding Window Maximum with a Monotonic Deque?

Problem and Applicable Scenarios

Given an integer array nums and a window size k, the first window covers indices 0 through k - 1. Move the window one position to the right at a time and return the maximum of each window. The constraints are 1 <= nums.length <= 100000 and 1 <= k <= nums.length. For example:

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
result = [3, 3, 5, 5, 6, 7]

The target is O(n) time and O(k) auxiliary space, excluding the output array. The standard problem guarantees a nonempty array and a valid k. If a production API must accept an empty array or invalid k, define the return value or exception separately instead of mixing unspecified behavior into the algorithm proof.

Multiple Chinese- and English-language interview-preparation resources published in 2026 still use Sliding Window Maximum as a direct monotonic-deque exercise and ask candidates to explain the front element, expired indices, back eviction, and amortized complexity. A Chinese public solution published in 2026 also compares the brute-force and deque approaches. The core skill is general algorithm and data-structure reasoning, so the correct category is coding; the TypeScript example does not make it a frontend question.

What the Interviewer Is Evaluating

First, can you recognize the structure: one element enters and one leaves on every move, while an extreme value must remain available? Brute force rescans the k - 1 elements shared by adjacent windows. A monotonic deque keeps only indices that can still become the current or a future maximum.

Second, can you explain why the deque stores indices instead of values alone? Expiration depends on position, and equal values can come from different positions. Without indices, you cannot reliably tell whether the maximum at the front has left the window.

Third, can you prove that a back element may be removed permanently? If j < i and nums[j] <= nums[i], the newer element is at least as large and expires later. Whenever both are in a window, the older element cannot win. This is a domination argument, not merely a way to make the deque look sorted.

Finally, complexity requires amortized analysis. One iteration can remove several indices, so an individual iteration is not strictly O(1). Each index enters once and leaves at most once from either end, however, so all deque operations together take O(n) time.

Clarifying Questions Before Answering

• Is the window size fixed? It is fixed at k; a variable window needs a revised expiration rule and query contract.
• Can the array be empty? The standard constraints exclude it; an extended API should explicitly return an empty array or reject the input.
• Is k guaranteed to be valid? The problem says yes; the sample implementation still validates it at runtime to prevent invalid lengths or out-of-bounds access.
• Can values repeat or be negative? Yes. The algorithm relies only on comparisons and indices, not positivity or uniqueness.
• Should equal values keep the newer or older index? Either yields correct maxima. This solution removes the older equal value and keeps the index that expires later.
• Must auxiliary space actually be O(k)? Yes. A JavaScript array that only advances a head pointer without reclaiming old slots may retain O(n) storage; this solution uses a circular buffer of capacity k.
• Do we return values or maximum indices? The main problem returns values. If indices are required, return the front index and define the tie rule for duplicate maxima.
• May the input be modified? No. The implementation only reads nums.

30-Second Answer Framework

“I will keep candidate indices in a deque. Indices increase from front to back, while their values strictly decrease. At index i, I first remove expired indices from the front. I then remove indices from the back while their values are less than or equal to nums[i], because the new element is at least as large and expires later. After pushing i, the front value is the answer once the first full window exists. Each index is pushed once and removed at most once, so total time is O(n). The deque contains at most k indices, giving O(k) auxiliary space.”

Step-by-Step Deep Dive

Step 1: Use baseline approaches to locate the repeated work.

When both n and k approach 100000, brute force can perform roughly 10^10 comparisons. A heap is a useful intermediate answer, but it maintains priority among all entries. This problem only reads the maximum, so an older candidate dominated by a newer entry has no future value.

Step 2: State the domination rule precisely.

Suppose j < i and nums[j] <= nums[i]. In every future window containing both indices, the value at j cannot exceed the value at i. As the window moves right, j also expires before i. Therefore, from the moment i arrives, j can never become a window maximum again and may be removed permanently from the candidate set.

Using less-than-or-equal in the removal condition retains only the newest index for equal values and makes deque values strictly decreasing. Removing only strictly smaller values is also correct, but then values are merely nonincreasing and multiple equal candidates remain. The proof and code must use the same strategy.

Step 3: Maintain four checkable invariants.

After processing index i:

1. Indices in the deque strictly increase and follow arrival order.
2. Every stored index lies in the current range [i - k + 1, i].
3. Corresponding array values strictly decrease from front to back.
4. Every removed index from the current window has a later, not-smaller candidate remaining along its domination chain.

The first three properties make the front the largest retained candidate. The fourth shows that no discarded element could have been the true maximum. Together, they establish that the front represents the entire window, not merely the largest element inside the deque.

Step 4: Implement a circular deque that actually uses O(k) space.

export function maxSlidingWindow(
  nums: readonly number[],
  k: number,
): number[] {
  if (!Number.isInteger(k) || k < 1 || k > nums.length) {
    throw new RangeError("k must be an integer between 1 and nums.length");
  }

  const deque = new Int32Array(k);
  let head = 0;
  let size = 0;
  const result: number[] = [];

  for (let i = 0; i < nums.length; i += 1) {
    while (size > 0 && deque[head] <= i - k) {
      head = (head + 1) % k;
      size -= 1;
    }

    while (size > 0) {
      const back = (head + size - 1) % k;
      if (nums[deque[back]] > nums[i]) break;
      size -= 1;
    }

    deque[(head + size) % k] = i;
    size += 1;

    if (i >= k - 1) {
      result.push(nums[deque[head]]);
    }
  }

  return result;
}

The circular buffer has exactly k slots. Expired entries are removed before each push, so the current window contains at most k - 1 valid indices before writing the new one; the push cannot overwrite the front. Int32Array can store indices up to the stated maximum of 100000. If a variant permits indices beyond the 32-bit range, use a regular numeric array or revise the input contract.

Step 5: Prove that each reported value is the true window maximum.

The deque starts empty, so all invariants hold. When a new index arrives, front removal discards only elements outside the current window. Back removal applies the domination rule: every removed element is replaced by the newer, not-smaller index i. Pushing i preserves increasing indices and strictly decreasing values.

The first complete window exists at i = k - 1. From then on, the front is always inside the window. Strictly decreasing deque values make it larger than every other retained candidate, while domination chains ensure that every unretained element is no larger than some retained candidate. Therefore nums[deque[head]] is the current maximum. Induction over all i proves that all n - k + 1 outputs are correct.

Step 6: Trace duplicates and the expiration boundary.

For the example, each entry below is index:value:

i=0  [0:1]                  no full window yet
i=1  [1:3]                  3 dominates 1
i=2  [1:3, 2:-1]            output 3
i=3  [1:3, 2:-1, 3:-3]      output 3
i=4  [4:5]                  1 expires; 5 dominates -1 and -3; output 5
i=5  [4:5, 5:3]             output 5
i=6  [6:6]                  6 dominates 5 and 3; output 6
i=7  [7:7]                  7 dominates 6; output 7

For [4, 4, 4] with k = 2, the second 4 removes the first, and the third removes the second. The deque always contains the newest index, while both windows still return 4. This case checks the equal value condition and exposes why storing values alone cannot track expiration correctly.

Step 7: Give the amortized complexity accurately.

The two while loops do not multiply the complexity to O(nk). Every index is pushed once and never returns after removal, so all front and back removals together occur at most n times. Total time is O(n). The circular deque stores at most k indices, so auxiliary space is O(k). The output has n - k + 1 entries and is normally excluded from auxiliary-space analysis.

Step 8: Use a naive oracle for differential testing.

Fixed cases should cover k = 1, k = n, all equal values, strictly increasing and decreasing arrays, all-negative values, and the standard mixed example. An empty array and k = 0 are invalid inputs and should throw RangeError. Then generate short random arrays and a random valid k, and compare every output with a naive implementation that scans each window. The randomized check should verify both result length and the value for every window.

For very small n or a single window, brute-force scanning is shorter and easier to review. If the language provides a reliable deque, prefer that standard container. The circular buffer appears here so the TypeScript implementation's physical storage bound matches its O(k) analysis.

Strong Sample Answer

“Brute force scans k elements for every window, which is O(nk) in the worst case. I would maintain a monotonic deque of indices. Indices increase in arrival order, while their values strictly decrease from front to back.

At index i, I first remove every front index less than or equal to i - k, because it has expired. I then remove indices from the back while their values are less than or equal to nums[i]. The new element is at least as large and leaves the window later, so those older elements can never become a maximum again. I push i, and once i >= k - 1, the front gives the current maximum.

Correctness follows from two facts: front removals are outside the window, and each back removal has a newer, not-smaller replacement that survives longer. Because retained values decrease, the largest remaining candidate is at the front. Each index enters once and leaves at most once, so total time is O(n). The deque stores at most k indices, giving O(k) auxiliary space. I would test k = 1, k = n, duplicate values, monotone arrays, and negative numbers, then compare randomized cases against a brute-force oracle.”

Common Mistakes

• Store only values in the deque → Equal values cannot be distinguished at expiration → Store indices and read values from the array.
• Maintain decreasing values but never remove expired fronts → An old maximum keeps appearing after it leaves the window → Clean the front using i - k on every iteration.
• Use < i - k as the expiration test → The index equal to i - k is already left of the window → Use less-than-or-equal.
• Call the nested while loops O(nk) → An index cannot be removed repeatedly → Use the fact that each index enters and leaves at most once.
• Use shift() and claim constant-time removal → JavaScript may move array elements on a front deletion → Use a standard deque, head pointer, or circular buffer.
• Advance a head pointer without reclaiming storage and claim O(k) space → The backing array can still grow to O(n) → Use circular storage with fixed capacity k.
• Mismatch the equal-value rule and proof → Strictly decreasing and nonincreasing invariants get mixed → State that this solution removes older values with less-than-or-equal.
• Put values alone in a heap → Lazy deletion still cannot identify expired entries → A heap approach must store indices too.
• Test only the standard example → Boundary errors in k = 1, duplicates, and decreasing arrays remain hidden → Add fixed boundaries and a randomized oracle.

Follow-Up Questions and Responses

Follow-up 1: Why is it safe to remove an older equal value?

The newer index has the same value and necessarily expires later. In every window containing both, either index supplies the same maximum. The older one leaves first and cannot regain an opportunity after the newer one expires. Keeping only the newer index is therefore safe and shortens the deque.

Follow-up 2: What if the result must include the first occurrence of each maximum?

Do not remove older equal values. Remove only strictly smaller values from the back, making deque values nonincreasing. The front then keeps the earliest maximum in the current window. If the result needs the last occurrence, retain this solution's less-than-or-equal removal. The tie rule changes, but the O(n) bound does not.

Follow-up 3: Why not use a max heap?

A heap is a valid quick solution when it stores values and indices and performs lazy deletion. Expired entries that are not at the top remain allocated, so an ordinary binary heap can grow to O(n) space and takes O(n log n) time. An indexed heap with arbitrary deletion can achieve O(n log k) time and O(k) space, but it is more complex. In an interview, the heap can be a useful intermediate answer before optimizing to a monotonic deque.

Follow-up 4: What if every window needs both its maximum and minimum?

Maintain two independent deques: one with decreasing values for the maximum and one with increasing values for the minimum. Each index still enters and leaves each deque at most once, so total time remains O(n) and auxiliary space remains O(k).

Follow-up 5: What if the window size changes on every query?

If both boundaries still move only to the right, use the current left boundary to remove expired indices and the monotonic deque still works. If the window can expand leftward, candidates that were permanently discarded may reenter the range and cannot be recovered. Use a balanced tree, segment tree, or offline range-maximum-query structure according to the update and query pattern.

Follow-up 6: How would you process an infinite stream online?

Assign an increasing sequence number to every arrival, apply the same expiration and back-removal steps, and emit the front value after the kth element and on every later arrival. Store at most k candidate indices and values, so memory is independent of total stream length. Out-of-order arrivals would additionally require an event-time window, watermark, and late-data policy; that is outside the ordered-array model of this problem.

Follow-up 7: How does this pattern extend to bounded dynamic programming?

For a recurrence where the current state equals its own cost plus the maximum of the previous k states, keep a deque ordered by DP value. The front supplies the transition maximum, while expiration still depends on the index. The comparison target changes from nums[i] to dp[i], but the proof still relies on a later, not-smaller state dominating an older state.