My bracket check says ([)] is fine

New to some of the words above? Open a quick recap. Each takes about two minutes.

Quick recapBig-O in two minutes· 2 min

Big-O says how the work grows as the input grows. One loop over n items is O(n): twice the items, twice the work. A loop inside a loop is O(n²): twice the items, four times the work. Space is the same idea for the extra memory: a few numbers is O(1), a copy of the input is O(n). The full lesson: My code passed every test, then timed out on the big one.

Quick recapLists in two minutes· 2 min

A list keeps items in order, and you can change it. append(x) adds at the end and pop() takes from the end: both O(1). insert(0, x) and pop(0) work at the front, so every other item moves one place: O(n). xs[-1] is the last item, and an empty list is false, so not xs asks whether it’s empty.

xs = ['a', 'b']
xs.append('c')   # ['a', 'b', 'c']
xs[-1]           # 'c'
xs.pop()         # 'c', and xs is ['a', 'b'] again
xs.insert(0, 'z')  # ['z', 'a', 'b']: 'a' and 'b' each moved
not []           # True

See the problem

The interview task: say whether a string of brackets is valid, with every bracket closed by the same kind, in the right order. You count them:

def is_valid(s):
    return all(s.count(a) == s.count(b) for a, b in ['()', '[]', '{}'])

It says (()) is valid and (() isn’t. Then the interviewer tries ([)], and it says True. One of each kind opens and closes, but the ) comes while [ is still open. It says True for )( too.

Counting forgets the order. To know what a ) may close, you need to know which bracket opened last and is still open.

Define the task

Write is_valid(s).

• Input: a string of up to 400,000 brackets, each one of ( ) [ ] { }. It can be empty.
• Output: True if every bracket is closed by one of the same kind, in the right order. Otherwise False.
• The hard part: it must be fast for 400,000 brackets, however deep they nest.

Examples: is_valid('{[()()]}') is True. is_valid('([)]') is False.

Pause and think

⏸ Pause and think

Before you write any code: you read the string from left to right, and a closing bracket comes. Which opening bracket must it close?

Give it two minutes with pen and paper before you open a hint.

Hints open one at a time:

Hint 1 of 3

It must close the last opening bracket that isn’t closed yet. In ([)], that’s [, so the ) comes too soon.

Hint 2 of 3

Keep the open brackets in a list. A new one goes at the end. A closing one checks the end, then takes it off.

Hint 3 of 3

At the end, the list must be empty: a bracket still in it was never closed.

Understand the idea

A stack: the last in is the first out. Think of a pile of plates. You put a plate on top, and take one from the top. A stack has two moves: push puts an item on top, and pop takes the top one off. You never reach under the top.

Brackets close last-opened first. In {[()]}, the ( opened last, so it must close first. So push each opening bracket. When a closing one comes, the bracket it must close is on top: check that they match, and pop it. That’s one pass, O(n). The stack holds the brackets still open, so it’s as tall as the deepest nesting: O(n) memory at worst.

In Python, a list is a stack, with its top at the end. stack.append(x) pushes, stack.pop() pops, stack[-1] looks at the top, and not stack asks whether it’s empty. Each is O(1): the end of a list has room to grow, and no other item moves.

The front is the wrong end. stack.insert(0, x) and stack.pop(0) make a stack too, but each moves every other item one place: O(d) for a stack d items deep. For first in, first out, a queue, Python has collections.deque: that’s the next lesson.

Python runs your code on a stack. Each function call goes on the call stack, and comes off when it returns: the last call made is the first to finish. That’s why deep recursion runs out of room, and why any recursion can become a loop with your own stack, as the recursion lesson shows.

Stacks fit whenever the newest open item is the next to deal with: brackets and HTML tags, undo, the back button, .. in a path, working out a sum, and walking a maze as deep as it goes. A stack can also hold the items still waiting for something, like days waiting for a warmer one: that’s the second practice problem.

Watch it. The panel shows the stack, with its top on the right. Try your own brackets, like ([)] or ((.

A stack of open brackets

⤢ Full view

1. {0
2. [1
3. (2
4. )3
5. (4
6. )5
7. ]6
8. }7

Work so far

stack, top on the right	empty
most on it at once	0
items moved	0

Step 1 of 10. Read the brackets from left to right. An opening one goes on the stack. A closing one must match the bracket on top, which comes off. Question: This string has 8 brackets. At most, how many will be on the stack at once?

What happens next? This string has 8 brackets. At most, how many will be on the stack at once?

238Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def is_valid(s: str) -> bool:
2    opener = {")": "(", "]": "[", "}": "{"}
3    stack = []  # the top is stack[-1]
4    for ch in s:
5        if ch in opener:
6            if not stack or stack[-1] != opener[ch]:
7                return False
8            stack.pop()
9        else:
10            stack.append(ch)
11    return not stack

Try your own input

BracketsShow it

★A stack remembers what’s still open

When the newest open item is the one to deal with next, keep the open items on a stack: push when one opens, pop when it closes. In Python, that’s a list, used at its end.

Climb the ladder

All three check '{[()()]}'. What changes is how much they copy or move, and for which strings.

Okay

Cut out a pair, and look again

The idea: Find a pair next to each other, like () or [], and cut it out. Repeat. A valid string ends up empty. If no pair is left but the string isn’t empty, it isn’t valid.

It’s how you’d check by hand: the innermost pair is always side by side, and cutting it out makes the next one side by side.

def is_valid(s: str) -> bool:
    while s:
        for pair in ("()", "[]", "{}"):
            i = s.find(pair)
            if i != -1:
                break
        if i == -1:
            return False  # no pair is left next to each other
        s = s[:i] + s[i + 2 :]  # cut the pair out
    return True

Time

O(n²)

Space

O(n)

Why

Each cut searches from the left again and makes a new string of what’s left. So n/2 cuts copy about n²/4 characters, whatever the shape, and the searches add more.

Where it breaks: every cut searches and copies the rest of the string. 200,000 pairs side by side, {}{}{}…, take 200,000 cuts. Each one first looks for () and [] all the way through, then copies up to 400,000 characters: tens of billions of steps. It runs out of time.

Better

A stack, with its top at the front

The idea: Push each opening bracket with insert(0, ch), at the front. For a closing bracket, check that stack[0] matches, and take it off with pop(0). Empty at the end means valid.

The waste in Okay: after every cut, it starts over and copies the rest. A stack remembers which brackets are still open, so one pass is enough.

Top at the front: every push moves the stack

⤢ Full view

1. (0
2. (1
3. [2
4. ]3
5. )4
6. )5

Work so far

stack, top on the left	empty
most on it at once	0
items moved	0

Step 1 of 8. Read the brackets from left to right. An opening one goes on the stack. A closing one must match the bracket on top, which comes off.

◀ BackPlayNext ▶Reset Ask me first Show as text

1def is_valid(s: str) -> bool:
2    opener = {")": "(", "]": "[", "}": "{"}
3    stack = []  # the top is stack[0]
4    for ch in s:
5        if ch in opener:
6            if not stack or stack[0] != opener[ch]:
7                return False
8            stack.pop(0)
9        else:
10            stack.insert(0, ch)
11    return not stack

Try your own input

BracketsShow it

Highlighted lines are new in this rung.

def is_valid(s: str) -> bool:
    opener = {")": "(", "]": "[", "}": "{"}
    stack = []  # the top is stack[0]
    for ch in s:
        if ch in opener:
            if not stack or stack[0] != opener[ch]:
                return False
            stack.pop(0)
        else:
            stack.insert(0, ch)
    return not stack

Time

O(n · d)was O(n²)

Space

O(n)

Why

One pass, but insert(0, x) and pop(0) move every item already on the stack. With up to d brackets open, each step moves up to d items: O(n · d), and O(n²) when it nests all the way.

What changed from the previous rung

def is_valid(s: str) -> bool:
    while s:
        for pair in ("()", "[]", "{}"):
            i = s.find(pair)
            if i != -1:
                break
        if i == -1:
            return False  # no pair is left next to each other
        s = s[:i] + s[i + 2 :]  # cut the pair out
    return True
    opener = {")": "(", "]": "[", "}": "{"}
    stack = []  # the top is stack[0]
    for ch in s:
        if ch in opener:
            if not stack or stack[0] != opener[ch]:
                return False
            stack.pop(0)
        else:
            stack.insert(0, ch)
    return not stack

Where it breaks: deep nesting. 200,000 brackets deep, ((( … ))), put up to 200,000 items on the stack, so the pushes and pops move about 40 billion items. It runs out of time on the deep speed test, though pairs side by side are quick.

Best

A stack, with its top at the end

The idea: Push with append(ch). For a closing bracket, check that stack[-1] matches, and take it off with pop(). Empty at the end means valid.

The waste in Better: it works at the front of the list, so every step moves the rest. At the end of a list, items come and go without moving anything else.

Highlighted lines are new in this rung.

def is_valid(s: str) -> bool:
    opener = {")": "(", "]": "[", "}": "{"}
    stack = []  # the top is stack[-1]
    for ch in s:
        if ch in opener:
            if not stack or stack[-1] != opener[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

Time

O(n)was O(n²)

Space

O(n)

Why

One pass, and append() and pop() are O(1): no other item moves. The stack holds the brackets still open: n at worst, as for ((((.

What changed from the previous rung

def is_valid(s: str) -> bool:
    opener = {")": "(", "]": "[", "}": "{"}
    stack = []  # the top is stack[0]
    stack = []  # the top is stack[-1]
    for ch in s:
        if ch in opener:
            if not stack or stack[0] != opener[ch]:
            if not stack or stack[-1] != opener[ch]:
                return False
            stack.pop(0)
            stack.pop()
        else:
            stack.insert(0, ch)
            stack.append(ch)
    return not stack

When Best isn’t best: with only one kind of bracket, a counter is enough: add 1 for (, take 1 for ), and fail if it goes below 0 or doesn’t end at 0. That’s O(1) memory. With several kinds, the stack is what knows which kind is open.

Write it yourself

Now write it in the page. Press Run tests to check your code. Python runs in your browser, so nothing is sent anywhere. Your code is saved in this browser for next time.

Try Okay from the ladder first: it runs out of time on the pairs side by side. Better passes that one, but runs out of time on the deep one.

Check the brackets

Ctrl + Enter runs

def is_valid(s: str) -> bool: # True if every bracket is closed by the same # kind, in the right order. return False

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: is_valid('()') → True
2. ○Not run yet: is_valid('()[]{}') → True
3. ○Not run yet: is_valid('{[()()]}') → True
4. ○Not run yet: is_valid('([)]') → False
5. ○Not run yet: is_valid(')(') → False
6. ○Not run yet: Extra test
7. ○Not run yet: Extra test
8. ○Not run yet: Extra test
9. ○Not run yet: Speed test: 200,000 pairs side by side: {}{}{}… → True
10. ○Not run yet: Speed test: 200,000 brackets deep: ((( … ))) → True

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

is_valid()Run onceVisualize

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: cut out pairs	O(n²)	O(n)	Easy to see why it’s right	Copies the rest of the string after every cut	A short string, checked by hand
Better: a stack, top at the front	O(n · d), for d brackets open at most	O(n)	One pass, and as quick as Best when the nesting is shallow	insert(0, x) and pop(0) move every item on the stack: O(n²) when it nests all the way	The front is cheap, as in a linked list or a deque
Best: a stack, top at the end	O(n)	O(n)	One pass, and nothing else moves	A stack as tall as the deepest nesting	Always, with a Python list

How much work is that? Each bar is one rung, for n brackets nested as deep as they go, Better’s worst case. Pick a size, or run the race.

Checking n brackets nested all the way

1. OkayCut out a pair · O(n²)≈ 40,000,000,000 characters copied

2. BetterTop at the front · O(n · d)≈ 40,000,000,000 items moved

3. BestTop at the end · O(n)≈ 400,000 steps

At n = 400,000, Okay does about 100,000 times more work than Best.

Every bar does the same number of steps per second, so the race shows which rung finishes first. Turn on Log scale to compare the short bars.

Nested all the way, Better moves as many items as Okay copies characters. For pairs side by side, or any string that doesn’t nest deep, Better moves almost nothing, while Okay still copies about n²/4 characters.

The race gives every step the same time, but real steps differ. In this page’s Python, 40,000 brackets nested 20,000 deep take Okay about 0.7 to 0.9 seconds. Better takes about 0.1 to 0.3: Okay’s searches from the left cost more than Better’s moves. Outside the browser, the gap depends on the computer, and on some it flips. Either way, twice as deep takes both about 4 times as long. When the nesting is shallow, Better is as quick as Best. Best is the quickest at every size.

Common mistakes and edge cases

!stack[-1] on an empty list raises IndexError

Check not stack before you look at the top or pop. For )(, the ) comes with the stack empty, and stack[-1] raises IndexError: list index out of range. In the bracket check, an empty stack means the ) has nothing to close: return False.

• Check the stack at the end. (( never fails a match, so a loop that only checks closing brackets says it’s fine. return not stack catches the brackets still open.
• Counting works for one kind only. With just ( and ), a counter that never goes below 0 and ends at 0 is enough. With several kinds, a count can’t see that [ is still open when ) comes.
• An odd length is a quick no. A valid string has an even length, so len(s) % 2 == 1 can return False at once. It’s a shortcut, not a check: (] has an even length.
• A dict of pairs keeps it short. {')': '(', ']': '[', '}': '{'} gives each closing bracket its opening one, so one if handles all three kinds.
• Keep indices on the stack when you need places. To say where it fails, or how long each day waits, push the index, not the character.

Say it in the interview

Questions to ask first

• Which brackets can there be? Can there be other characters, like letters?
• Is an empty string valid?
• How long can it be, and how deep can it nest? Deep nesting rules out recursion.

A 60-second walkthrough

“I’ll use a stack: a Python list, with its top at the end. I read the string once. An opening bracket goes on the stack. A closing bracket must match the last bracket still open, which is the top: if the stack is empty or the top is a different kind, I return False, and otherwise I pop it. At the end, it’s valid only if the stack is empty, since anything left was never closed. A dict maps each closing bracket to its opening one. It’s O(n) time, and O(n) memory for a string nested all the way. append and pop at the end are O(1), so I don’t use the front of the list.”

Likely follow-ups

• Only round brackets? A counter is enough: add 1, take 1, never below 0, and 0 at the end. O(1) memory.
• Other characters, like code? Skip anything that isn’t a bracket. Strings and comments need more: a bracket inside quotes doesn’t count.
• Say where it fails? Push indices instead of characters. The first closing bracket that can’t match is the answer, or, at the end, the bracket left at the bottom of the stack.
• The fewest brackets to add to make it valid? Count the closing brackets with nothing to close, plus the brackets left on the stack.

Practice

Three problems, from easy to medium: typing with a backspace key, the next warmer day, and working out a sum written in reverse Polish notation. Each has hints, tests you can run here, and its own Okay, Better and Best answers. For each rung, say its Big-O before you open it.

1. Typing with backspace (easy)

Write same_after_backspace(a, b). Each string is what someone typed, where # is the backspace key: it deletes the character before it, if there is one. Return True if both end up as the same text.

Example: same_after_backspace('ab#c', 'ad#c') is True: both give ac. same_after_backspace('a#c', 'b') is False.

Hint 1 of 3

Type it out on a stack: a letter goes on, and # takes the last one off, if there is one.

Hint 2 of 3

The stacks hold every character kept: O(n) memory. Read from the end instead: there, a # tells you to skip the next character you meet.

Hint 3 of 3

Walk both strings from the end, each to its next character that no # deletes, and compare. Stop when either runs out.

Typing with backspace

Ctrl + Enter runs

def same_after_backspace(a: str, b: str) -> bool: # '#' deletes the character before it, if any. # True if a and b end up as the same text. return a == b

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: same_after_backspace('ab#c', 'ad#c') → True
2. ○Not run yet: same_after_backspace('ab##', 'c#d#'): both end up empty → True
3. ○Not run yet: same_after_backspace('a#c', 'b') → False
4. ○Not run yet: same_after_backspace('a##c', '#a#c'): a # at the start deletes nothing → True
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test
7. ○Not run yet: Extra test
8. ○Not run yet: Speed test: 'ab#' 300,000 times, against 'a' 300,000 times → True
9. ○Not run yet: Two strings of 400,000 letters, in 1 MB → True

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

same_after_backspace()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Cut out each #, with the character before it

The idea: Find the first #, cut it and the character before it out of the string, and repeat. Then compare the two strings that are left.

It does what the keys do, one backspace at a time.

def same_after_backspace(a: str, b: str) -> bool:
    return typed(a) == typed(b)


def typed(s: str) -> str:
    while "#" in s:
        i = s.index("#")
        s = s[: max(i - 1, 0)] + s[i + 1 :]  # cut the # and the character before it
    return s

Time

O(n²)

Space

O(n)

Why

Each cut copies the rest of the string, so up to n cuts copy up to n characters each.

Where it breaks: 'ab#' 300,000 times takes 300,000 cuts of up to 900,000 characters: about 180 billion copies. It runs out of time.

Better

Type each one onto a stack

The idea: For each character, push it, or, for a #, pop if the stack isn’t empty. Then compare the two stacks.

The waste in Okay: each cut copies everything after it. A stack only touches its top.

Highlighted lines are new in this rung.

def same_after_backspace(a: str, b: str) -> bool:
    return typed(a) == typed(b)


def typed(s: str) -> list[str]:
    stack = []
    for ch in s:
        if ch == "#":
            if stack:
                stack.pop()  # # deletes the last character kept
        else:
            stack.append(ch)
    return stack

Time

O(n + m)was O(n²)

Space

O(n + m)was O(n)

Why

One pass over each string, O(1) per character. The stacks hold every character that’s kept.

What changed from the previous rung

def same_after_backspace(a: str, b: str) -> bool:
    return typed(a) == typed(b)


def typed(s: str) -> str:
    while "#" in s:
        i = s.index("#")
        s = s[: max(i - 1, 0)] + s[i + 1 :]  # cut the # and the character before it
    return s
def typed(s: str) -> list[str]:
    stack = []
    for ch in s:
        if ch == "#":
            if stack:
                stack.pop()  # # deletes the last character kept
        else:
            stack.append(ch)
    return stack

Where it breaks: memory. Two strings of 400,000 letters and no # make two stacks of 400,000 items: megabytes, more than the 1 MB test allows.

Best

Walk both from the end

The idea: Read each string from its end. Count the #s you pass, and skip that many characters. Compare the next kept character of each, then step on.

The waste in Better: it stores every character, just to compare them. A # only deletes what’s before it, so reading from the end, you know at once whether a character stays.

Highlighted lines are new in this rung.

def same_after_backspace(a: str, b: str) -> bool:
    i, j = len(a) - 1, len(b) - 1
    while i >= 0 or j >= 0:
        i = last_kept(a, i)
        j = last_kept(b, j)
        if i < 0 or j < 0:
            return i < 0 and j < 0  # both ran out together
        if a[i] != b[j]:
            return False
        i -= 1
        j -= 1
    return True


def last_kept(s: str, i: int) -> int:
    """The index of the last character at or before i that no # deletes, or -1."""
    skip = 0
    while i >= 0:
        if s[i] == "#":
            skip += 1
        elif skip:
            skip -= 1
        else:
            break
        i -= 1
    return i

Time

O(n + m)

Space

O(1)was O(n + m)

Why

Each index only moves left, once over its string, and it keeps just two indices and a count.

What changed from the previous rung

def same_after_backspace(a: str, b: str) -> bool:
    return typed(a) == typed(b)
    i, j = len(a) - 1, len(b) - 1
    while i >= 0 or j >= 0:
        i = last_kept(a, i)
        j = last_kept(b, j)
        if i < 0 or j < 0:
            return i < 0 and j < 0  # both ran out together
        if a[i] != b[j]:
            return False
        i -= 1
        j -= 1
    return True


def typed(s: str) -> list[str]:
    stack = []
    for ch in s:
        if ch == "#":
            if stack:
                stack.pop()  # # deletes the last character kept
def last_kept(s: str, i: int) -> int:
    """The index of the last character at or before i that no # deletes, or -1."""
    skip = 0
    while i >= 0:
        if s[i] == "#":
            skip += 1
        elif skip:
            skip -= 1
        else:
            stack.append(ch)
    return stack
            break
        i -= 1
    return i

When Best isn’t best: when memory is fine, Better is simpler to get right. In an interview, say Better first, then improve it to this.

2. Daily temperatures (medium)

Write days_to_warmer(temps). temps[i] is the temperature on day i. For each day, return how many days you wait for a warmer one, or 0 if none comes.

Example: days_to_warmer([73, 74, 75, 71, 69, 72, 76, 73]) gives [1, 1, 4, 2, 1, 1, 0, 0]. Day 2 is 75, and the next warmer day is day 6, at 76: 4 days later.

Hint 1 of 3

For each day, look at the days after it until one is warmer. That’s O(n²) when the days keep getting colder.

Hint 2 of 3

Turn it around: when a warm day comes, which earlier days was it the answer for? Every day still waiting that’s colder than it.

Hint 3 of 3

Keep a stack of the days still waiting. Their temperatures go down toward the top, so a warm day pops every colder day off the top, and each pop is an answer.

Daily temperatures

Ctrl + Enter runs

def days_to_warmer(temps: list[int]) -> list[int]: # For each day, how many days until a warmer one? # 0 if none comes. return [0] * len(temps)

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: days_to_warmer([73, 74, 75, 71, 69, 72, 76, 73]) → [1, 1, 4, 2, 1, 1, 0, 0]
2. ○Not run yet: days_to_warmer([30, 40, 50, 60]) → [1, 1, 1, 0]
3. ○Not run yet: days_to_warmer([50, 50, 50]): the same isn’t warmer → [0, 0, 0]
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test
7. ○Not run yet: Speed test: 100,000 days, each colder than the day before
8. ○Not run yet: Speed test: 100,000 days, each colder, then one hot day

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

days_to_warmer()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Look ahead from each day

The idea: For each day, check the days after it one by one, and stop at the first warmer one.

It answers the question as asked, one day at a time. The list of answers doesn’t count as extra memory: every rung returns one.

def days_to_warmer(temps: list[int]) -> list[int]:
    waits = [0] * len(temps)
    for i in range(len(temps)):
        for j in range(i + 1, len(temps)):
            if temps[j] > temps[i]:
                waits[i] = j - i
                break
    return waits

Time

O(n²)

Space

O(1)

Why

A day that never gets a warmer one reads every day after it. When the days keep getting colder, that’s n(n − 1)/2 reads.

Where it breaks: 100,000 days, each colder than the day before: about 5 billion reads. It runs out of time.

Better

Look ahead only when a warmer day is coming

The idea: Walk from the last day back, keeping the warmest temperature after each day. If nothing after it is warmer, its answer is 0 at once. Otherwise, look ahead for it.

The waste in Okay: a day with no warmer day after it still reads to the end. The warmest temperature so far, from the right, tells you that at once.

Highlighted lines are new in this rung.

def days_to_warmer(temps: list[int]) -> list[int]:
    waits = [0] * len(temps)
    warmest_after = float("-inf")  # the warmest day after day i
    for i in range(len(temps) - 1, -1, -1):
        if temps[i] < warmest_after:  # a warmer day is coming, so look for it
            j = i + 1
            while temps[j] <= temps[i]:
                j += 1
            waits[i] = j - i
        warmest_after = max(warmest_after, temps[i])
    return waits

Time

O(n²)

Space

O(1)

Why

A day with nothing warmer after it costs one step, but a day that waits a long time still reads every day in between.

What changed from the previous rung

def days_to_warmer(temps: list[int]) -> list[int]:
    waits = [0] * len(temps)
    for i in range(len(temps)):
        for j in range(i + 1, len(temps)):
            if temps[j] > temps[i]:
                waits[i] = j - i
                break
    warmest_after = float("-inf")  # the warmest day after day i
    for i in range(len(temps) - 1, -1, -1):
        if temps[i] < warmest_after:  # a warmer day is coming, so look for it
            j = i + 1
            while temps[j] <= temps[i]:
                j += 1
            waits[i] = j - i
        warmest_after = max(warmest_after, temps[i])
    return waits

Where it breaks: put one hot day at the end, and every day has a warmer day coming, far away. Each reads to the end again: about 5 billion reads. A shortcut for one bad input doesn’t fix the worst case.

Best

A stack of the days still waiting

The idea: Walk the days in order, with a stack of the days that haven’t seen a warmer one. A new day pops every colder day off the top and gives each its answer, then goes on the stack itself.

The waste in Better: each waiting day reads the days in between by itself. With a stack, one warm day answers every colder day that’s waiting, at once. Its temperatures only go down toward the top, so it’s called a monotonic stack: a Core lesson has more problems like it.

Highlighted lines are new in this rung.

def days_to_warmer(temps: list[int]) -> list[int]:
    waits = [0] * len(temps)
    waiting = []  # days with no warmer day yet; the top is the coldest
    for day, temp in enumerate(temps):
        while waiting and temps[waiting[-1]] < temp:
            before = waiting.pop()
            waits[before] = day - before
        waiting.append(day)
    return waits

Time

O(n)was O(n²)

Space

O(n)was O(1)

Why

Each day goes on the stack once and comes off at most once: at most 2n pushes and pops in all.

What changed from the previous rung

def days_to_warmer(temps: list[int]) -> list[int]:
    waits = [0] * len(temps)
    warmest_after = float("-inf")  # the warmest day after day i
    for i in range(len(temps) - 1, -1, -1):
        if temps[i] < warmest_after:  # a warmer day is coming, so look for it
            j = i + 1
            while temps[j] <= temps[i]:
                j += 1
            waits[i] = j - i
        warmest_after = max(warmest_after, temps[i])
    waiting = []  # days with no warmer day yet; the top is the coldest
    for day, temp in enumerate(temps):
        while waiting and temps[waiting[-1]] < temp:
            before = waiting.pop()
            waits[before] = day - before
        waiting.append(day)
    return waits

When Best isn’t best: the stack can hold all n days. You can also walk from the end and jump ahead with the answers you already have, j += waits[j]. That needs no stack and is O(n) too, but it’s harder to explain.

3. Reverse Polish notation (medium)

Write eval_rpn(tokens). The tokens are a sum in reverse Polish notation, where each operator comes after its two numbers: ['2', '1', '+', '3', '*'] means (2 + 1) × 3, so the answer is 9. The operators are + - * /, and / rounds toward 0, so 7 / −2 is −3. The tokens always make a valid sum, and every number on the way fits in 32 bits, as in the interview task.

Hint 1 of 3

Read from the left. A number waits until an operator uses it. Which numbers does an operator use? The last two still waiting.

Hint 2 of 3

Keep the numbers waiting on a stack. An operator pops two, works them out, and pushes the answer.

Hint 3 of 3

The first number popped is the right one: for 3 4 -, pop 4, then 3, and push 3 − 4. For /, int(a / b) rounds toward 0, but a // b rounds down. a / b is a float, which is exact for numbers that fit in 32 bits.

Reverse Polish notation

Ctrl + Enter runs

def eval_rpn(tokens: list[str]) -> int: # Each operator comes after its two numbers. # / rounds toward 0. return 0

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: eval_rpn(['2', '1', '+', '3', '*']) → 9
2. ○Not run yet: eval_rpn(['4', '13', '5', '/', '+']) → 6
3. ○Not run yet: eval_rpn(['7', '-2', '/']): / rounds toward 0 → -3
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test
7. ○Not run yet: Speed test: 262,144 ones, added in pairs, then pairs of pairs, and so on → 262144
8. ○Not run yet: Speed test: 100,000 ones, then 99,999 plus signs: 1 1 1 … + + + → 100000

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

eval_rpn()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Work out the first operator, and look again

The idea: Find the first operator, put the answer in place of it and its two numbers, and repeat until one number is left.

The first operator always has its two numbers just before it, so each step is easy to check.

def eval_rpn(tokens: list[str]) -> int:
    items = list(tokens)
    while len(items) > 1:
        i = 0
        while items[i] not in ("+", "-", "*", "/"):
            i += 1  # find the first operator
        a, b = int(items[i - 2]), int(items[i - 1])
        items[i - 2 : i + 1] = [str(apply(items[i], a, b))]  # three items become one
    return int(items[0])


def apply(op: str, a: int, b: int) -> int:
    if op == "+":
        return a + b
    if op == "-":
        return a - b
    if op == "*":
        return a * b
    return int(a / b)  # rounds toward 0, as the task asks; exact while numbers fit in 32 bits

Time

O(n²)

Space

O(n)

Why

Each step searches from the left for the first operator, then moves every token after it: n/2 steps of up to n each, O(n²).

Where it breaks: 524,287 tokens take 262,143 steps, each moving up to 524,287 tokens: about 70 billion moves. It runs out of time.

Better

Work back from the last token

The idea: The last token is the last operator. Its right number is the sum that ends just before it, and its left number the sum before that: work out each with a call.

The waste in Okay: after each step, it searches again from the left and moves the rest. Working back from the end reads each token once.

Highlighted lines are new in this rung.

def eval_rpn(tokens: list[str]) -> int:
    value, _ = evaluate(tokens, len(tokens) - 1)
    return value


def evaluate(tokens: list[str], i: int) -> tuple[int, int]:
    """The value of the expression ending at tokens[i], and the index just before it starts."""
    token = tokens[i]
    if token not in ("+", "-", "*", "/"):
        return int(token), i - 1
    b, i = evaluate(tokens, i - 1)  # the right operand ends just before the operator
    a, i = evaluate(tokens, i)
    return apply(token, a, b), i


def apply(op: str, a: int, b: int) -> int:
    if op == "+":
        return a + b
    if op == "-":
        return a - b
    if op == "*":
        return a * b
    return int(a / b)  # rounds toward 0, as the task asks; exact while numbers fit in 32 bits

Time

O(n)was O(n²)

Space

O(n)

Why

Each token is read once, by one call. But the calls in progress go as deep as the sum nests: up to n/2, as for 1 1 1 … + + +

What changed from the previous rung

def eval_rpn(tokens: list[str]) -> int:
    items = list(tokens)
    while len(items) > 1:
        i = 0
        while items[i] not in ("+", "-", "*", "/"):
            i += 1  # find the first operator
        a, b = int(items[i - 2]), int(items[i - 1])
        items[i - 2 : i + 1] = [str(apply(items[i], a, b))]  # three items become one
    return int(items[0])
    value, _ = evaluate(tokens, len(tokens) - 1)
    return value


def evaluate(tokens: list[str], i: int) -> tuple[int, int]:
    """The value of the expression ending at tokens[i], and the index just before it starts."""
    token = tokens[i]
    if token not in ("+", "-", "*", "/"):
        return int(token), i - 1
    b, i = evaluate(tokens, i - 1)  # the right operand ends just before the operator
    a, i = evaluate(tokens, i)
    return apply(token, a, b), i


def apply(op: str, a: int, b: int) -> int:
    if op == "+":
        return a + b
    if op == "-":
        return a - b
    if op == "*":
        return a * b
    return int(a / b)  # rounds toward 0, as the task asks; exact while numbers fit in 32 bits

Where it breaks: depth. 100,000 ones, then 99,999 plus signs, nest 100,000 deep, and Python stops at about 1,000 calls in progress: RecursionError.

Best

A stack of the numbers waiting

The idea: Read from the left. Push each number. For an operator, pop the right number, then the left one, and push the answer. The last number on the stack is the answer.

The waste in Better: each call waiting holds a place on Python’s own call stack, which stops at about 1,000. Your own stack is a list, which can hold millions.

Highlighted lines are new in this rung.

def eval_rpn(tokens: list[str]) -> int:
    stack = []
    for token in tokens:
        if token in ("+", "-", "*", "/"):
            b = stack.pop()  # the right operand is on top
            a = stack.pop()
            stack.append(apply(token, a, b))
        else:
            stack.append(int(token))
    return stack.pop()


def apply(op: str, a: int, b: int) -> int:
    if op == "+":
        return a + b
    if op == "-":
        return a - b
    if op == "*":
        return a * b
    return int(a / b)  # rounds toward 0, as the task asks; exact while numbers fit in 32 bits

Time

O(n)

Space

O(n)

Why

One pass, O(1) per token. The stack holds the numbers still waiting: at most about n/2, as for 1 1 1 … + + +

What changed from the previous rung

def eval_rpn(tokens: list[str]) -> int:
    value, _ = evaluate(tokens, len(tokens) - 1)
    return value


def evaluate(tokens: list[str], i: int) -> tuple[int, int]:
    """The value of the expression ending at tokens[i], and the index just before it starts."""
    token = tokens[i]
    if token not in ("+", "-", "*", "/"):
        return int(token), i - 1
    b, i = evaluate(tokens, i - 1)  # the right operand ends just before the operator
    a, i = evaluate(tokens, i)
    return apply(token, a, b), i
    stack = []
    for token in tokens:
        if token in ("+", "-", "*", "/"):
            b = stack.pop()  # the right operand is on top
            a = stack.pop()
            stack.append(apply(token, a, b))
        else:
            stack.append(int(token))
    return stack.pop()


def apply(op: str, a: int, b: int) -> int:
    if op == "+":
        return a + b
    if op == "-":
        return a - b
    if op == "*":
        return a * b
    return int(a / b)  # rounds toward 0, as the task asks; exact while numbers fit in 32 bits

When Best isn’t best: it trusts its input. For a sum that might be wrong, check that each operator finds two numbers, and that just one number is left at the end.

Check yourself

A few quick questions. Ones you miss are remembered, so you can find your weak spots later.

1. Multiple choiceWhich of these strings of brackets is valid?

   ([)])({[]()}(()

   Check answer
2. Predict the outputWhat does this print?

   stack = []
   for x in [1, 2, 3]:
       stack.append(x)
   stack.pop()
   print(stack[-1])

   123IndexError

   Check answer
3. Spot the bugThis checks brackets with a stack. What's wrong?

   def is_valid(s):
       opener = {')': '(', ']': '[', '}': '{'}
       stack = []
       for ch in s:
           if ch in opener:
               if stack[-1] != opener[ch]:
                   return False
               stack.pop()
           else:
               stack.append(ch)
       return not stack

   For a closing bracket with nothing open, stack[-1] raises IndexErrorIt says (( is validIt's O(n²)Nothing

   Check answer
4. Pick the patternYou get the parts of a path, like ['home', 'ann', '..', 'bo', '.', 'docs'], where .. goes up a folder and . stays. Which folder does it end in? What fits best?

   A stack of folder names: push a name, pop for ..A set of the namesSort the parts firstTwo pointers from both ends

   Check answer
5. Multiple choiceA stack is kept with insert(0, x) and pop(0). 1,000 brackets are pushed, then all popped. About how many times does an item move one place?

   About 1,000About 2,000About 1,000,000Never

   Check answer

Flashcards

Add these to your review deck. Each card comes back a little later every time you get it right.

• Card 1What is a stack?Show answer
• Card 2How do you use a Python list as a stack?Show answer
• Card 3Why not insert(0, x) and pop(0)?Show answer
• Card 4How do you check brackets?Show answer
• Card 5What is a monotonic stack?Show answer
• Card 6How do you work out reverse Polish notation?Show answer

Add 6 cards to my review deck

Cheat sheet

• A stack is last in, first out: push on top, pop from the top, look at the top.
• In Python: stack.append(x), stack.pop(), stack[-1] and not stack. Each is O(1).
• Not insert(0, x) or pop(0): they move every other item, O(n). For a queue, use collections.deque.
• Brackets: push the opening ones; a closing one must match the top, and pops it; the stack must be empty at the end.
• Check not stack before stack[-1] or pop(), or you get IndexError.
• Push indices when you need places, like the days still waiting.
• A monotonic stack keeps its items in order, so a new item pops every item it beats: the next warmer day for each, in O(n).
• Any recursion can become a loop with your own stack, which isn’t stopped at about 1,000.

Go deeper

• In the Python docs: Using lists as stacks.
• Step through more: Bracket check on the DSA visualizer, with the stack’s top at each end.
• My power function crashes when n is 5,000 turns a recursion into a loop with a stack, in its practice.
• Next on the DSA roadmap: queues.

Can you do these now?

If you’re not sure of any of these, scroll back to that part before moving on.

• Say what last in, first out means, and spot a problem that needs it
• Use a Python list as a stack, with append() and pop() at its end
• Check brackets in one pass with a stack
• Keep a stack of items still waiting, to find the next warmer day

✓Mark as completeI already know this

Status: Not started