Next greater element and the monotonic stack in Python

Why it matters

Many list questions ask, for each item, about the nearest bigger or smaller item near it. How many days until the next warm day? How far back was the last higher price? Which bar of a histogram limits the rectangle? A direct answer for each item needs a scan, and the scans add up to O(n squared) time for n items. A monotonic stack, which is a stack that always stays in one order, answers all of these questions in one pass, which takes O(n) time. Interviewers expect it, and it appears in real systems that process streams of readings.

This lesson builds the idea from the simplest brute force, shows why most of the work can be thrown away, and then applies the same stack to four problems. The last one is a circular list, where the search wraps around. Python has no stack class that you need to import. A plain list does the job, because adding and removing at the end of a list is fast.

Words you will need

• Monotonic: moving in one direction only. A monotonic stack holds values that only increase, or only decrease, from bottom to top.
• Next greater element: for an item, the first item to its right that is strictly larger. "Strictly" means equal values do not count.
• Previous smaller element: for an item, the nearest item to its left that is strictly smaller.
• Span: a count of how many consecutive days ending today satisfy a rule. The lesson defines it when it appears.
• Circular list: a list where the item after the last one is the first one again.
• Amortized: averaged over a whole sequence of operations. One operation may cost more, but the average cost per operation stays small.
• Index: the position of an item in a list, starting from 0.
• Negative index: a position counted from the end. a[-1] is the last item, and a[-2] is the item before it.
• Truthy: Python treats some values as true and some as false in an if test. An empty list is false, and a list with at least one item is true. So if stack: means "if the stack is not empty".

The first principle: hidden values can be dropped

Picture a row of people at a concert, all standing up, each one wanting to see the nearest person in front of them who is taller than they are. You are the person at the back, looking forward, and you want to know who is the first taller person ahead.

Now think about who matters to the people behind you. Suppose someone in the row is tall, and there is a shorter person between them and you. The shorter person is hidden by the tall one. For anyone behind you, the tall person is closer and also taller, so the shorter person can never be the answer for anyone behind. You can forget the shorter person.

That idea is the whole method. When you scan the list, some values become useless as soon as a bigger, nearer value arrives. Throw them away. The values you keep form a list in a fixed order, and a stack is the natural way to keep that list, because the newest value always sits on top, and removal happens only at the top.

The brute force first

Before the clever method, write the simple one. For each position, look to its right until you find a bigger value. If you find none, the answer is -1.

For [4, 5, 2, 25], the answers are 5, 25, 25 and -1. Here is the work for the first item, 4. The scan checks 5 and stops, because 5 is bigger. The answer is 5, and that took one comparison. For the item 2, the scan checks 25 and stops. For the item 25, nothing is to its right, so the answer is -1.

Now consider a list of n items in decreasing order, such as [9, 8, 7, 6, 5]. No item has a bigger value to its right, so each scan runs to the end. The first item scans 4 items, the second scans 3, and so on. The total is 4 + 3 + 2 + 1 = 10 comparisons for 5 items. For n items it is about n squared divided by 2, which is O(n squared). Doubling the input makes the work about four times as large.

The clever method avoids repeating scans, and it does so by remembering what earlier scans learned.

The idea, precisely

Scan the list from right to left. Keep a stack of candidates: values that might be the next greater element for items still to the left. Before you process item x, the stack holds the candidates from the items to its right, with the nearest one on top.

For the current item x, pop every candidate that is not bigger than x. These candidates are smaller or equal, so they are hidden behind x for everything further left. They have no future. When you stop popping, the top of the stack is the first item to the right that is strictly bigger than x, and it is the answer for x. If the stack is empty, there is no bigger item, so the answer is -1. Finally, push x onto the stack, because x is now a candidate for the items on its left.

The stack therefore stays in one order from bottom to top: values get smaller as you go up. That is why it is called monotonic. The top holds the smallest candidate.

Here is the proof that dropping values is safe, written in plain words. Suppose a value y is in the stack, and a newer value x is at a position closer to the current item, with x at least as big as y. For any item k to the left, if y is bigger than k, then x is also bigger than k, and x is closer. So x is always a better answer than y. The value y can never be the answer, so removing it loses nothing.

The Python list as the stack

A Python list can be used as a stack with two methods. stack.append(x) pushes x on top, at the end of the list. stack.pop() removes the last item and returns it, which is the top. To read the top without removing it, use stack[-1]. Both append and pop work at the end of the list, and both take constant time on average, which is what this method needs.

stack[-1] on an empty list does not return None or 0. It raises an error. The code in this lesson always checks if stack before it reads the top. The mistakes section shows the error you get when the check is missing.

Worked example 1: trace [4, 5, 2, 25]

Here is the trace from the right. Each row shows the stack before the current item is handled, then the answer, then the stack after the item is pushed. The stack is written bottom to top, so the top is on the right.

The answers, read from position 0 to 3, are 5, 25, 25, -1. That matches the brute force.

Read the table row by row. The value 2 is removed as soon as 5 arrives, because it is hidden behind 5. The row for position 1 is the moment the method pays for its speed: one pop removes a candidate for good.

The same idea from the left: previous smaller values

Sometimes the question asks for the nearest smaller value to the left. The method is the mirror image. Scan from the left, pop every value that is >= the current one, and read the top. The top is the nearest earlier value that is strictly smaller. If the stack is empty, the answer is -1. Then push the current value.

Trace [6, 3, 4, 5, 2]. The stack holds values, shown bottom to top.

The answers are -1, -1, 3, 4 and -1. At position 4, the value 2 pops everything, because every earlier value is at least as large as 2. Nothing smaller sits to its left, so the stack is empty and the answer is -1.

The left-to-right version and the right-to-left version follow one rule. Pop every value that cannot be an answer, then read the top. Only the direction of the scan and the comparison change. Here is the method as a complete program. It has no input, so you can run it:

[-1, -1, 3, 4, -1]
[-1, 1, 2]

The code has the same shape as the next-greater code below, with the scan reversed and the comparison flipped. Practice exercise 2 asks you to adapt the idea to a different comparison.

The code

Type this into the Input box. The first line is the number of values. The second line holds the values.

4
4 5 2 25

5 25 25 -1

The loop runs from the last index down to 0. The while loop pops every value that is <= the current item. The comparison uses <= because the question asks for a strictly greater value, so equal values must be removed. The line res[i] = stack[-1] if stack else -1 reads the answer before the current item is pushed, so an item never answers for itself.

The expression stack[-1] if stack else -1 is a conditional expression. It reads as "the top if the stack has something in it, otherwise -1". The and in the while line stops at the first false part. So stack[-1] never runs on an empty stack.

The first line of input is read with int(input()), but the value is not used. The length of the list comes from len(a), so the count is not needed. The line still has to be read, so that the next input() call gets the second line.

The last line joins the answers with spaces. str(v) turns each number into text, because " ".join only accepts text pieces.

Why the loop is still O(n)

The inner while loop looks like it could make the method O(n squared). Count the work instead of the loops. Every value is pushed exactly once, in the outer loop. Every value is popped at most once, because once it is popped it is gone for good. So the total number of pops is at most the total number of pushes, which is n. The total work is the number of pushes plus the number of pops, which is at most 2n. That is O(n).

Try it on [5, 4, 3, 2, 1, 9], scanned from the right. The 9 is pushed first. The value 1 pops nothing, because 9 is bigger. Each later arrival pops the value that came just before it. That makes six pushes and four pops, ten steps for six values.

Computer scientists call this amortized cost. A single pop can remove many values, so one iteration of the outer loop can be slow. But the slow iterations can only happen as often as values are removed, and each value is removed once. Averaged over all the work, each item costs a constant amount.

Worked example 2: daily temperatures, scanning left to right

Scanning from the right works well for "next greater". For a related question, scanning from the left is more natural. Suppose you have the daily temperatures of a week, and for each day you want the number of days to wait until a warmer day. Day 0 is the first day.

The left-to-right method stores the positions of days that are still waiting for a warmer day. The stack holds positions, and their temperatures decrease from bottom to top. When a new day is warmer than the day on top, the waiting day is resolved. Its answer is the difference between the two positions. Keep popping while the new day is warmer than the top. Then push the new day's position, because it now waits for a warmer day too.

Type this into the Input box:

8
73 74 75 71 69 72 76 73

1 1 4 2 1 1 0 0

The function enumerate(t) gives a pair on each step: the position i and the temperature temp. It saves writing t[i] in the loop, and it makes the position visible.

Trace the important steps. Day 0 is 73 and goes on the stack. Day 1 is 74, which is warmer than 73. The day 0 is resolved with 1 - 0 = 1 days, and day 1 is pushed. Day 2 is 75, which resolves day 1 with 2 - 1 = 1 day. Day 3 is 71 and is pushed on top of day 2. Day 4 is 69 and is pushed. Day 5 is 72. It is warmer than 69, so day 4 resolves with 5 - 4 = 1 day. It is also warmer than 71, so day 3 resolves with 5 - 3 = 2 days. It is not warmer than 75, so the loop stops, and day 5 is pushed. Day 6 is 76, which resolves days 5 and 2. The days left on the stack, 6 and 7, keep the answer 0 in the list.

Notice that the code stores idx and reads the temperature through t[stack[-1]]. That is the reason the stack holds positions. If it held temperatures alone, you could not compute the distance i - idx.

Worked example 3: stock span, a two-step question

A stock span is a classic question. For each day, it asks how many consecutive days up to and including today had a price no higher than today's price. Consider prices 100, 80, 60, 70, 60, 75, 85. The spans are 1, 1, 1, 2, 1, 4, 6. On day 5, the price 75 is no higher than the last four prices (60, 70, 60, 75), and the price 80 before them is higher than 75, so the span is 4.

This question needs two steps of thinking. The first step is to see that the span equals today's position minus the position of the nearest earlier price that is strictly higher. If there is no such price, the span is everything up to today. The second step is to find that earlier position quickly. That is exactly the "previous greater element" question, solved by a monotonic stack that stores positions.

Type this into the Input box:

7
100 80 60 70 60 75 85

1 1 1 2 1 4 6

Check day 5, which has price 75 at position 5. The loop pops positions with prices <= 75: position 4 (60) and position 3 (70) are popped. Position 2 (60) is already gone, because day 3 popped it. The top is now position 1, with price 80, which is strictly higher. So the span is 5 - 1 = 4. The expression i - stack[-1] if stack else i + 1 handles the case with no higher price before: then the span covers all i + 1 days from the start.

The code is the monotonic stack from worked example 1. The stack holds positions, because the answer needs a distance. The pop condition still uses <=, which means "not higher than today" when it compares prices.

Worked example 4: a circular list

Sometimes the list wraps around. In a circular list, the item after the last one is the first one. For [1, 2, 1, 4, 3], the next greater element of the last item, 3, is found by wrapping around to the start: the values after it are 1, 2, 1, 4, so the answer is 4. The item 4 at position 3 has no greater value anywhere, so its answer is -1.

The fix is to walk the list twice. Use i % n to turn an index from 0 to 2n - 1 into a real position. The % operator gives the remainder after division, so 7 % 5 is 2, and the index wraps back to 0 at the end. The loop starts at the far end of the doubled list, so its first n steps only fill the stack with candidates from the wrapped copy. Its last n steps visit the real positions 0 to n - 1, and only those steps write answers. The loop goes from 2 * n - 1 down to 0, and it writes an answer only when i < n.

The call range(2 * n - 1, -1, -1) counts down from 2 * n - 1 to 0. The second number is where the count stops, and that stop value is not included. This is why the stop value is -1 and not 0.

Type this into the Input box:

5
1 2 1 4 3

2 4 4 -1 4

Follow the last real position, which is 4. The loop reaches i = 4 after its wrapped steps. The value is 3, and the stack (top on the right) is [4, 2, 1]. The pops remove 1 and 2, because both are <= 3. The top is then 4, so the answer for position 4 is 4. The answer for position 3 is -1, because the value 4 has nothing strictly bigger, even after wrapping around.

The walk costs 2n steps, and each step pushes and pops at most once. So the circular version is still O(n), but with a larger constant.

A stack that is monotonic, not sorted

A monotonic stack is not a sorted list. Its items are not sorted by position in the input. They are sorted by value from bottom to top, because the pops always remove the values that would break that order. After the right-to-left scan of [4, 5, 2, 25] is finished, the stack holds [25, 5, 4], with 25 at the bottom and 4 on top. Read from bottom to top, the values only get smaller. That shape makes the top the nearest useful candidate.

The input [4, 5, 2, 25] is not sorted at all, yet the stack has a clean order at the end. The pops enforce that order. Each push adds one value at the top, so the order holds after every step.

Strictly or not: the one symbol that changes the answer

The pop test decides what counts as "greater". With <= in the test, equal values are popped, so the answer must be strictly greater. Change the test to <, and equal values stay on the stack. An equal value then becomes the answer, so the method computes "next greater or equal" instead.

Look at the broken version in the common mistakes section. For [2, 2], it printed [2, -1]. That output is correct for a different question. The first 2 has an equal value to its right, so under the "greater or equal" rule its answer is 2. The symbol is therefore a choice about the problem, not a detail of the code. Read the wording of the question carefully. "Strictly greater" needs <= in the pop test. "Greater or equal" needs <.

The stock span follows the same care. A span counts days whose price is no higher than today's, so equal prices stay in the count. That is why the span code uses <= in its pop test, as in worked example 3. The span is the distance back to the nearest strictly higher price.

What happens inside

Each pass through the outer loop does one push. The inner loop does zero or more pops. The stack holds candidates in order, so the top is always the nearest candidate. The memory used is a list of answers, which is n values, and a stack that can reach n values in the worst case, such as a strictly decreasing list in the left-to-right scan. So the space is O(n).

A Python list stores a reference to each number, not the bare number. Each number is an object with its own memory, so a list of a million integers uses noticeably more memory than a list of a million values stored side by side in a compact array. The time bound does not change. If memory matters for a large input, the array module stores plain numbers in a compact form, but the code in this lesson does not need it.

The method works on indexes or values, and the choice affects the code. Values are enough when you only need to compare, as the next-greater solution does. Indexes are required when you need a distance, a position in another list, or the span. A good habit is to ask, before you write the stack, "Do I need the value or the position for my answer?"

Common mistakes

Using < where <= belongs. For the next-greater problem, a value equal to the current one is not greater, so it must be popped. With <, the answer for equal values is wrong. Here is the real output of a version with < on the input [2, 2]:

[2, -1]

The first 2 has no strictly greater value to its right, so the correct answer is -1. The version with < gives 2, because it kept the equal value on the stack.

Reading the top of an empty stack. Suppose you write stack[-1] without checking that the stack has an item. Python does not return a default. It stops with an error. Here is the real message from a tiny program that does this:

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    print(stack[-1])
          ~~~~~^^^^
IndexError: list index out of range

The last line gives the error type, IndexError, and the reason. The lines above it show where it happened. The line numbers and file name depend on your program. The fix is to test if stack first, as every version in this lesson does.

Using a negative index by accident. A position of -1 does not mean "nothing". Python reads it as the last item, and it writes there without any error. If a sentinel value of -1 reaches a place where a real position is expected, the program quietly changes the last item. Here is a small example with the real output:

res = [0, 0, 0]
res[-1] = 5
print(res)

[0, 0, 5]

The last slot was changed, and no error was raised. When an answer looks wrong at the end of a list, check for a -1 that was used as a position.

Pushing values when you need distances. The daily-temperatures and stock-span answers are distances, so the stack must store positions. If it stores temperatures, you lose the positions and cannot compute i - idx.

Thinking the nested loop means O(n squared). Count the pushes and pops, not the loops. Each value moves on and off the stack at most once.

Writing the answer into the wrong slot. In the left-to-right version, the answer belongs to the popped position, res[idx], not to the current position res[i]. Writing res[i] = i - idx gives the distance for the wrong day. The output looks plausible but is shifted. Check one row of your output by hand before you trust the method.

Forgetting that leftovers keep their default value. In daily temperatures, days that are never resolved keep 0 in the answer list, which is correct. If your code sets a different default, check that the answer for the last items still matches the problem.

Debugging walkthrough

Suppose you wrote the next-greater function with stack[-1] < a[i] in the pop test, and your output for [2, 2] is [2, -1], but you expected [-1, -1]. Trace it by hand, with the stack written after each step.

Start at the right. Position 1 holds 2. The stack is empty, so the answer is -1, and 2 is pushed: [2]. Position 0 holds 2. The stack top is 2. The pop test is stack[-1] < a[i], so 2 < 2 is false, and nothing is popped. The answer is the top, 2. That is the bug. The equal value was not treated as hidden.

The fix is to change < to <=. Then 2 <= 2 is true, the top is popped, the stack is empty, and the answer is -1, which is right.

A useful habit is to write the condition in words before you code it. "Pop while the top is not strictly greater than the current value." Written that way, <= is the obvious choice, and the bug in the condition is easy to see.

Variations and edge cases

Choose the direction by asking what you need. A question about the next item to the right fits a scan from the right, because the stack then holds exactly the candidates that lie to the right of the current item. A question about an earlier item fits a scan from the left, for the same reason.

Previous smaller element. Scan from the left and pop values that are >= the current item. The top is then the nearest earlier value that is strictly smaller. This is the mirror of next greater.

Next smaller element. Scan from the right and pop values that are >= the current item, reading the top after the pops. The top is the first value to the right that is strictly smaller.

Empty list. With n = 0, the loops do not run and the result is an empty list. The code handles this without a special case, but test it. The one-line max in the practice section is different: max([]) raises an error, so it needs a check for an empty list first.

All values equal. For [3, 3, 3], the next-greater answers are all -1, because no value is strictly bigger. The stack empties at each step.

Strictly increasing values. For [1, 2, 3, 4], each value's answer is the next value. The left-to-right daily-temperatures method resolves each day as soon as the next one arrives.

Equal prices in the stock span. For [5, 5, 5] the spans are 1, 2 and 3. The pop test uses <=, so an equal earlier price is popped, and the stack empties. Each day then counts every day back to the start. Equal prices extend the span, as the question asks.

Strictly decreasing values. For [4, 3, 2, 1], the next-greater answers are all -1. The right-to-left scan pops the previous value each time, so the stack never holds more than one value.

Interview view

When you see a problem asking "for each item, the nearest bigger or smaller one", say the rule first: "I need the nearest candidate that beats the current item, and anything the current item hides can be dropped." Then name the structure: "A monotonic stack, scanning from one end." Write the loop, the pop condition, the answer read, and the push. Then give the complexity: O(n) time, because every value is pushed and popped at most once, and O(n) space in the worst case.

Say the rule aloud as you code. For example: "I scan from the right. Before I push the current value, I remove every candidate that is not strictly bigger, because the current value hides it." That sentence explains why the code is right, and it gives the interviewer something to check.

Interviewers often follow up with a larger question. The stock span is one. The largest rectangle in a histogram is harder, and the histogram lesson later in this module covers it. A third is "sum of minimums over all subarrays", which uses both the previous smaller and the next smaller element for each value. When you reach a harder version, check whether it reduces to asking the nearest smaller or bigger neighbour for each item. If it does, the monotonic stack applies.

Real-world uses

Stock and sensor data. A span or a "days since higher" count tells an analyst how unusual today's reading is. It runs in one pass over a stream, so it works on live data.

Weather and temperature logs. "Days until a warmer day" is a direct question about a log of readings, and the left-to-right method answers it in one pass.

Histograms and image analysis. The largest rectangle under a row of bars is a standard way to find the biggest block of solid colour in a binary image. It relies on the previous smaller and next smaller values for each bar.

Complexity summary

The brute force uses no extra space, but it is too slow for large inputs. The monotonic stack trades a little memory for a large saving in time.

Practice

Work on paper first, then check your answer against the solution.

Exercise 1. Find the next smaller element to the right for [4, 5, 2, 25]. Write the answers and the stack after each step.

Show the answer

The answers are 2, 2, -1, -1. Scan from the right, pop values that are >= the current item, and read the top. For 25 the stack is empty, so -1, and the stack becomes [25]. For 2, the 25 is >= 2, so it is popped. The stack is empty, so -1, and the stack becomes [2]. For 5 the top is 2, which is smaller, so the answer is 2, and the stack becomes [2, 5]. For 4, the 5 is >= 4, so it is popped. The top is now 2, which is smaller, so the answer is 2. The final stack is [2, 4].

Exercise 2. Solve "previous greater element" by scanning from the left. For each item, the answer is the nearest earlier item that is strictly bigger. Use -1 when none exists.

Show the answer

def previous_greater(a):
    res = []
    stack = []
    for value in a:
        while stack and stack[-1] <= value:
            stack.pop()
        res.append(stack[-1] if stack else -1)
        stack.append(value)
    return res

The top after popping is the nearest earlier value that is strictly bigger, so it is the answer. For [4, 5, 2, 25] this gives [-1, -1, 5, -1].

Exercise 3. For [1, 2, 1, 4, 3] with the circular method, predict the answer for each position before you run it. Then check it.

Show the answer

The answer is 2 4 4 -1 4. Position 0 (value 1) sees 2 next. Position 1 (value 2) sees 4. Position 2 (value 1) also sees 4, because the 2 is behind it and 4 comes next. Position 3 (value 4) has nothing bigger, even after wrapping, so -1. Position 4 (value 3) wraps around and sees 4.

Exercise 4. Change days_to_wait so that it returns the number of days until a day that is at least as warm as today, using <= in the comparison. Predict how the output changes for 73 74 75 71 69 72 76 73.

Show the answer

Change the pop condition to t[stack[-1]] <= temp. For the given input, the answers stay 1 1 4 2 1 1 0 0, because that input has no repeated temperature. For the input 70 70, the first day's answer becomes 1 instead of 0, so the output is 1 0.

Exercise 5. Write a function days_until_higher(p) that returns, for each day, the number of days after it until a price at least as high. Use 0 when none.

Show the answer

def days_until_higher(p):
    n = len(p)
    res = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and p[stack[-1]] < p[i]:
            stack.pop()
        res[i] = stack[-1] - i if stack else 0
        stack.append(i)
    return res

The stack holds positions, so the distance is the top position minus the current one. For [1, 2, 1, 4, 3] the answer is [1, 2, 1, 0, 0].

Exercise 6. Write a function next_greater_index(a) that returns, for each item, the index of the next greater element to its right, or -1 when there is none. For [4, 5, 2, 25] the answer is [1, 3, 3, -1].

Show the answer

def next_greater_index(a):
    n = len(a)
    res = [-1] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and a[stack[-1]] <= a[i]:
            stack.pop()
        res[i] = stack[-1] if stack else -1
        stack.append(i)
    return res

The stack holds indexes, so the answer is an index. Compare with a[stack[-1]] to read the value at that index.

Exercise 7. Explain in your own words why a value removed from the stack can never be the answer for a later item. Use the concert-row picture.

Show the answer

A removed value is shorter than, or equal to, a newer value that stands closer to any later item. For any later item looking to the left, the newer value is nearer and at least as tall. So the removed value is always hidden, and the nearer value wins.

Exercise 8. The next-greater code uses stack[-1] <= a[i] in its pop test. Write the version that returns the next greater or equal element, and state the one change.

Show the answer

Change the pop test to stack[-1] < a[i]. Then equal values stay on the stack and answer the question. For [2, 2] the output becomes [2, -1]. The rest of the code is the same.

Exercise 9. For the input 3 1 4 1 5 9 2 6, use the next-greater code to find the answers for positions 0 and 5, and say which values are popped at position 5.

Show the answer

Position 0 has 3, and the next greater value is 4 at position 2, so the answer is 4. Position 5 has 9, and nothing to its right is bigger, so the answer is -1. Before position 5, the stack holds [6, 2], with 2 on top. Position 5 pops 2 and then 6, because both are <= 9. The stack is then empty, so the answer is -1.

Exercise 10. Write a function max_span_days(p) that returns the largest value of the stock span over all days. For 100 80 60 70 60 75 85, the answer is 6.

Show the answer

def max_span_days(p):
    return max(stock_span(p))

It reuses stock_span from worked example 3. The function max returns the largest item of a list. It raises an error on an empty list, so a program that can receive an empty list needs a check first. The largest span for the input above is 6, on the last day.

What you now know

• A monotonic stack keeps candidates in one order, so the top is always the nearest useful value.
• A Python list works as the stack. append pushes, pop removes the top, and stack[-1] reads it without removing it.
• Scanning from the right, pop values that are not strictly greater, then read the top as the next greater element.
• Scanning from the left with positions answers distance questions, such as days to wait and the stock span.
• A value removed from the stack is hidden behind a nearer, bigger value, so it can never be an answer again.
• Every value is pushed once and popped at most once, so the whole method is O(n), even with a loop inside a loop.
• A circular list is handled by walking the list twice with i % n, and writing answers only in the first pass.

The next lesson moves to queues. It shows how to build a queue from two lists, how a circular list can hold a fixed-size queue, and how collections.deque works at both ends.