Deque and the sliding window maximum

Why it matters

A stack works at one end, and a queue works at two ends in a fixed pattern: add at the back, remove at the front. A deque lets you add and remove at both ends freely. That extra freedom is what makes it the right tool for one of the best-known interview problems, the sliding window maximum. In that problem you must report the largest value in every window of k consecutive numbers as the window moves along an array. A naive solution takes O(n times k) time. A deque solves it in O(n), and the reasoning behind that answer is the most important idea in this module. This lesson builds the deque from first principles, explains how the window problem uses it, and ends with variations that interviewers like to ask.

The deque: a line open at both ends

A deque (pronounced "deck") is short for double-ended queue. It is a line of items where people can join or leave from either end. Think of a queue at a bus stop that has two doors. Passengers can board from the back or from the front, and the one at the front can get off first, or the one at the back can.

The deque supports six operations, all O(1):

• push_back(x): add at the back.
• push_front(x): add at the front.
• pop_back(): remove the back item.
• pop_front(): remove the front item.
• front() and back(): read the front or back item without removing it.
• empty() and size(): check whether it is empty, and how many items it holds.

A stack is a deque that uses only one end. A queue is a deque that uses one end to add and the other end to remove. The deque can do both jobs at once, which is why it solves problems that neither a stack nor a queue can solve alone.

The C++ standard library provides std::deque in the <deque> header. The first program below uses every kind of operation so you can see them together.

Output:

1 3 3
2
2

Trace it. Start empty. push_back(2) gives 2. push_back(3) gives 2 3. push_front(1) puts 1 at the front, giving 1 2 3. The first line reads the front (1), the back (3), and the size (3). Then pop_front() removes 1, leaving 2 3, and pop_back() removes 3, leaving 2. So front() is 2 and d[0] is 2. Unlike a queue or a stack, a deque also allows d[i], which reads the item at position i from the front. That index access is what lets the window algorithm look at the middle of the structure when it needs to.

What happens inside a deque

A vector stores its items in one block of memory. Adding at the back is cheap, but adding at the front would require moving every item one place, which is O(n). The deque avoids that problem by storing its items in several blocks of fixed size, with a small table of pointers to the blocks. The table has room at both ends, so the deque can grow in either direction. When one block is full at the front, a new block is added at the front of the table. Nothing already stored needs to move.

The cost is a slightly more complex structure, and random access by index is a little slower than a vector. For the algorithm in this lesson, that cost is small, and the O(1) operations at both ends are the essential feature.

The same structure also explains why std::stack and std::queue use a deque by default. They need fast operations at one or both ends, and the deque provides them. You will not usually care about the blocks, but knowing they exist helps you understand why a deque never needs to shift its items.

The sliding window problem

Here is the problem in plain words. You have an array of numbers, and a window size k. The window covers k consecutive numbers, and it starts at the left end. You report the maximum inside the window. Then the window slides one step to the right, and you report the maximum again. You keep going until the window reaches the right end.

For the array 1 3 -1 -3 5 3 6 7 with k = 3, there are six windows:

So the answer is 3 3 5 5 6 7. There are n - k + 1 windows in total, which is 6 for n = 8 and k = 3.

The naive method scans every window and finds its maximum. Each window has k values, and there are about n windows, so the work is about n times k. If k is half the array, that is O(n squared) in the worst case. For an array of a few hundred thousand values, that is too slow.

The idea: keep only the candidates

The key question is which values in the window can ever be the maximum. Suppose a value x at position i is in the window, and a larger value y appears later, at position j, where j is greater than i. Then y stays in the window at least as long as x does, because it is further to the right. So x can never be the maximum after y arrives. It is useless, and it can be thrown away.

That observation gives the deque plan. Keep a deque of indexes whose values are in decreasing order from front to back. The front is always the largest value still in the window. The rest of the deque holds the values that might become the maximum later, after the current maximum leaves the window.

For each new index i, do three things:

1. Drop expired. If the index at the front is outside the window, remove it from the front. The window covers indexes i - k + 1 to i, so an index at i - k or earlier is outside it.
2. Drop useless. While the back index holds a value smaller than the new value, remove it from the back. Those values can never be the maximum again.
3. Add. Push i at the back. Once i is at least k - 1, the window is full, and the value at the front is the answer for this window.

The three steps use both ends. Expiry works at the front, and the useless check works at the back. That is the reason a deque is needed. A queue cannot remove from the back, and a stack cannot remove from the front.

The diagram below shows the deque contents for the first few windows of the example, so you can see the same behaviour as a picture.

The array 1 3 -1 -3 5 3 6 7 with the sliding window of size 3 over the first six positions, and the deque of indexes beside each window

The window maximum in code

The program below implements the three steps. The function returns the list of maxima, and main prints it on one line.

Output:

3 3 5 5 6 7
4

The first line is the example from the problem, and it matches the table above. The second line uses a window as large as the whole array, so there is only one window, and its maximum is 4.

Here is the trace for the first line, one step per index. The table shows the deque after each step as a list of index and value pairs, with the front on the left.

Read the row for index 4 slowly, because it shows both ends at work. The index 1 was at the front, and it is now outside the window that ends at index 4. The step removes it from the front. Then the value 5 is bigger than the values at the back, 3 and -1, so both are removed from the back. Only the new index 4 is left, and it is the maximum of the window.

Notice what the deque never holds. The value 3 at index 1 was useful for windows 0 to 2 and 1 to 3. As soon as the 5 arrived, the 3 at index 1 could never win again, because 5 is larger and stays in the window at least as long. The algorithm forgets it immediately, and that is why the deque stays small.

Why it is O(n)

Each index is pushed onto the deque exactly once, when the loop reaches it. Each index is removed at most once, either from the front when it expires, or from the back when a bigger value arrives. Once removed, an index never returns. So the total number of pushes is n, and the total number of pops is at most n. Each step does a constant amount of other work. The total is O(n).

The same amortised argument as the queue lesson applies. A single step may pop many items from the back, but those items were each pushed earlier, and each push is counted once. The space is O(k) in the worst case, because the deque never holds more than the indexes inside the current window, plus the newest index.

A minimum at the same time

A common follow-up asks for the minimum of every window too. You can solve it with a second deque, with the comparison flipped. Keep indexes whose values increase from front to back. Drop from the back while the back value is bigger than the new value. The front is the minimum.

The next program does both at once. It reads n and k, then the array, and prints the maxima on one line and the minima on the next. Type the input exactly as shown.

Input box:

8 3
1 3 -1 -3 5 3 6 7

Output:

3 3 5 5 6 7
-1 -3 -3 -3 3 3

The minima row can be checked the same way as the maxima. The first window is 1 3 -1, whose minimum is -1. The second is 3 -1 -3, with minimum -3. The windows -1 -3 5 and -3 5 3 both have minimum -3. The window 5 3 6 has minimum 3, and 3 6 7 has minimum 3.

The two deques are independent. They share the same index i and the same expiry rule, but each one keeps its own candidates. This is a good pattern to remember: when two statistics come from the same window, use two monotonic structures in step.

Palindromes with a deque

A deque can check a palindrome, a word that reads the same forwards and backwards, such as racecar. Compare the first character with the last. If they match, remove both and compare again. If they ever differ, the word is not a palindrome. This uses front and back together, which a stack or a queue alone could not do in one structure.

The program below reads words, one per line, and prints YES or NO for each. Type the three words in the Input box.

Input box:

racecar
abca
x

Output:

YES
NO
YES

The constructor deque<char> d(s.begin(), s.end()) copies the characters of the string into the deque, in order. Then each round compares the two ends. For abca, the first round compares a with a and removes both, leaving bc. The second round compares b with c, which differ, so the answer is NO. A single character is always a palindrome, so the loop stops when one item is left.

The while (cin >> s) loop is a useful pattern. It reads words until the input ends, so the program works for any number of lines. This is the same reading style you saw in the earlier lessons, with a different stopping rule.

Choosing the right structure

After five lessons, you can match problems to structures. Keep a table like this one in your notes.

The main question to ask is which ends you need, and in which order items must leave. If the newest leaves first, use a stack. If the oldest leaves first, use a queue. If both ends matter, use a deque.

Tracing the minimum deque step by step

The minimum version uses the same three steps with the comparison flipped, so it is a good test of whether you understand the method rather than the code. Trace it on the example 1 3 -1 -3 5 3 6 7 with k = 3. The minimum deque keeps indexes whose values increase from front to back, and the table shows it after each index.

The minima are -1 -3 -3 -3 3 3. Read the row for index 6 with care, because it is the expiry case. The front index 3 has value -3, and it sits at 6 - 3 = 3, which is the boundary. The window that ends at index 6 starts at index 4, so index 3 is gone. The front is now index 5, with value 3. The window now holds the values 5, 3 and 6, and its minimum is 3, as printed.

Compare this table with the maximum table earlier. The rules are the same, and only the comparisons differ. That symmetry is useful. If you can trace one, you can trace the other by flipping the signs in your head.

Two deques, one window

The two-deque program computes the maximum and the minimum in one pass. Each deque has its own candidate list, but both use the same expiry rule. Both are updated for index i in the same loop iteration, and both read the same window. This is why the program can print two lines from one scan of the array.

The shared expiry rule matters. If one deque expired indexes with <= and the other with <, the two answers would describe different windows, and the output would be wrong in a way that is hard to notice. A useful check is that both deques always hold indexes from the same window, between i - k + 1 and i. You can verify it by printing the indexes after each step on a small example.

Use two deques, not one deque with both kinds of values, because the two lists have different rules. The maximum deque removes smaller values from its back, and the minimum deque removes bigger values from its back. Mixing them would remove useful candidates. Two separate structures keep the rules simple, and each rule is easy to prove.

Testing the window code

Window problems have many edge cases, so test them with a plan. Start with the smallest possible inputs, such as one value with k = 1. Then test the case where the window is the whole array, k = n, which should print one value. Then test a window that is one smaller than the array, which should print two values. These small cases catch off-by-one errors quickly.

For a stronger test, write a brute-force version that scans each window and finds its maximum directly, as in the earlier naive method. Run both versions on many random arrays with values from -5 to 5, and with small values of k. Small values create many duplicates, which are the cases where < and <= differ. When the outputs disagree, print the array and the window size, and trace the deque by hand on that array.

Finally, test a long input once, to check the time. With n equal to 200,000, the deque version should finish almost at once, while the naive version with k in the thousands would take many seconds. If your program is slow on a long input, check that each index is pushed once and that you never copy the deque inside the loop. A copy inside the loop turns an O(n) algorithm into an O(n times k) one, and it is easy to do by accident when you pass the deque to a helper function by value.

What if k is larger than the array?

The problem statement requires 1 <= k <= n, so this case should not occur. Still, a careful program handles it. If k is larger than n, there are no complete windows. The loop never reaches i >= k - 1, so nothing is printed, and the output is an empty line. Decide what the statement wants in that case, and write the check explicitly rather than relying on the loop to do nothing by accident.

Common mistakes

Mistake 1: storing values in the deque. If the deque holds values, you cannot tell when an item has left the window. Store indexes, and read the value with a[index] when you need it.

Mistake 2: the wrong expiry boundary. The window of size k that ends at index i covers indexes i - k + 1 to i. So an index equal to i - k has just left the window. The buggy program in the next section shows what happens when the test is one step too loose.

Mistake 3: reporting before the first full window. The first answer is valid only when i >= k - 1, which is when the window has k values. Printing earlier gives extra output lines that are not in the answer.

Mistake 4: using a queue for a sliding window. A queue lets you remove from the front only. The window also needs removals from the back, when a bigger value arrives. Only a deque provides both.

Mistake 5: using std::deque index access in place of front and back. Both work, but d[0] is the front and d[d.size() - 1] is the back. Mixing them up is easy, so use front() and back() in the algorithm to make the intent clear.

Mistake 6: forgetting the < versus <= choice. Dropping the back on < keeps equal values in the deque, which is fine for the maximum. It changes which index is kept, not the answer. Pick one rule and check it against a test with equal values.

The buggy expiry test

Here is a window maximum with one character changed. The expiry test uses < where it should use <=. The bug lets an index stay one step too long. Predict the output for the input 5 1 1 1 with k = 2 before you run it. The correct answer is 5 1 1.

Output:

5 5 1

The second answer is wrong. The window at index 2 covers positions 1 and 2, which hold 1 and 1, so the maximum is 1. But the buggy code still has index 0, which holds 5, at the front of the deque. The test dq.front() < i - k becomes 0 < 0 when i is 2, and that is false, so the index that should have expired stays. The answer 5 is printed when it should be 1.

Trace the fix. With <=, the test becomes 0 <= 0, which is true, so index 0 is removed. Then the answer for i = 2 comes from the next candidate, and it is 1. The lesson is that the expiry rule decides which index is at the front, and an off-by-one error there gives a plausible but wrong answer. Always test the first window that just stopped containing the biggest value.

Interview questions and what they test

Interviewers ask about deques to check your choice of structure and your ability to prove a bound.

• Sliding window maximum. Explain the deque of candidate indexes, the two kinds of removal, and the O(n) argument. This is the most common question in this module.
• Sliding window minimum. Use the flipped comparison with a second deque, and note that both windows can be computed in one pass.
• Valid palindrome. Compare the two ends and move inward. Mention that a deque makes the two-ended check clear.
• Why not a queue or a stack? The window needs removal from both ends, and only a deque provides both. Give that reason in one sentence.
• What about a very large k? When k is close to n, the window covers almost everything, and the deque may hold many candidates. The complexity is still O(n) because each index is pushed and popped once.

When you explain the window solution, describe the invariant first: the deque always holds the candidates for the current window, in decreasing order of value. Then show that each step keeps that invariant. Interviewers listen for that reasoning more than for the code.

Variations and edge cases

Test your window code with these cases:

• k = 1. Each window is a single value, so the output equals the input.
• k = n. There is one window, and the answer is the maximum of the whole array.
• All values equal. The deque should keep only the newest index in most steps, and the maxima should all be the same value.
• A strictly increasing array. Each new value removes everything before it, so the deque holds one item.
• A strictly decreasing array. Nothing is removed from the back, so the deque holds the whole window.
• Negative values only. The algorithm does not depend on sign, so the answers should still be correct.

The last test catches a common mistake: initialising the answer with 0 when the maximum might be negative. Always start from the actual values in the array.

Real-world uses

Monitoring systems compute the highest reading in the last few minutes, updated every second, which is exactly a sliding window maximum. Signal-processing code computes local peaks and troughs this way. Work-stealing schedulers, which share tasks among processors, use deques so that a worker takes its own tasks from one end and other workers take from the other end. The two-ended behaviour is the feature that makes these designs efficient.

Practice

1. Easy. Trace a deque through these operations: push_back(1), push_front(2), push_back(3), pop_front(). What are the front and back at the end?

2. Easy. For the window size k = 3, how many windows does an array of 10 values have?

3. Easy. Why does the sliding window program print nothing for the first k - 1 values?

4. Medium. Change the window maximum so that it prints the window sums instead. Hint: use a running sum, and add the new value and remove the expired one.

5. Medium. Explain why a deque holding indexes, not values, is necessary for the expiry test, using the example 5 1 1 1 with k = 2.

6. Medium. Write a function that tells whether a string can be turned into a palindrome by removing at most one character. Hint: use the two-ended check, and when the ends differ, try removing one of them.

7. Medium. Given k and an array, print the minimum of each window, computed with one deque. Hint: flip the comparison in the three-step plan.

8. Medium. Explain why std::stack and std::queue use std::deque by default, and why a plain std::vector would be a worse choice for a queue.

9. Hard. Explain why the three-step window algorithm is O(n) even though the drop-from-back loop can remove many items at once.

10. Hard. Find the maximum of every window of size k in a circular array, where the window can wrap from the end back to the start. Hint: the lesson's circular trick from the monotonic stack lesson can be combined with the deque, by walking through the array twice.

Module summary

• A stack is LIFO, a queue is FIFO, and a deque works at both ends. All core operations are O(1).
• Balanced brackets: push openers, and match each closer against the top.
• A monotonic stack solves next greater, next smaller and span problems in O(n).
• A queue can be built from two stacks, with amortised O(1) operations.
• A circular queue reuses slots with modulo arithmetic, and it must track full and empty correctly.
• A deque of indexes solves the sliding window maximum and minimum in O(n).