My rate limiter let 200 requests through in one second

DSA · Foundations
25 min read, about 1 h 15 min with practice

Concept
Asked often: high
Reviewed 2026-11

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 and deque in two minutes· 2 min

A list is quick at its end: append(x) and pop() are O(1). At its front, pop(0) and insert(0, x) move every other item one place: O(n). collections.deque is quick at both ends: append(x) and popleft() are O(1), and so are appendleft(x) and pop(). q[0] is the front item, and an empty deque is false.

from collections import deque

q = deque([1, 2])
q.append(3)    # deque([1, 2, 3])
q.popleft()    # 1, and q is deque([2, 3])
q[0]           # 2: the front
not deque()    # True

See the problem

The interview task: an API lets each user make 100 requests a second. Write the check. You count the requests in each clock second:

def allow(times, limit, window):
    out, counts = [], {}
    for t in times:
        block = t // window  # which second t is in
        if counts.get(block, 0) < limit:
            counts[block] = counts.get(block, 0) + 1
            out.append(True)
        else:
            out.append(False)
    return out

The times are in milliseconds. It turns away the 101st request in a second. Then a client sends 100 requests at 999 ms and 100 more at 1,000 ms. The first 100 count for second 0, the next 100 for second 1, and all 200 go through, 1 ms apart.

A clock second is the wrong window. The limit is for any 1,000 ms in a row: the last 1,000 ms, which moves on with every request.

Define the task

Write allow(times, limit, window).

Input: times, up to 600,000 request times in ms, in order. Several can share a ms. limit and window are at least 1.
Output: a list with True for each request that goes through, and False for each one turned away. A request at t goes through if fewer than limit went through in the last window ms: after t − window, up to t. A request turned away doesn’t count.
The hard part: it must be fast for 600,000 requests, however many fit in the window.

Example: allow([1, 2, 3, 1000, 1001, 1002], 3, 1000) is [True, True, True, False, True, True]. At 1,000 ms, the three before it are still in the last 1,000 ms. At 1,001 ms, the one at 1 ms has left.

Pause and think

Hints open one at a time:

Hint 1 of 3

The oldest. Requests come in order, so they leave the window in the order they went through: first in, first out.

Hint 2 of 3

Keep the requests that went through in the last window, oldest first. Before each new one, take the old ones off the front.

Hint 3 of 3

Then it’s a count: if fewer than limit are left, the request goes through, and joins the back.

Understand the idea

A queue: the first in is the first out. Think of a line at a shop. People join at the back, and the one at the front is served first. A queue has two moves: append adds at the back, and popleft takes from the front. Nobody skips ahead.

The requests in a window make a queue. They leave the last window ms in the order they came. So keep them in a queue: before each request, take every one at or before t − window off the front. What’s left is the window, and its length is the count. Each request joins once and leaves once: O(n) for all of them. The queue never holds more than limit.

A Python list is a slow queue. append() at the back is O(1), but pop(0) at the front moves every other item one place left: O(k) for k items. With 250,000 in the window, each pop(0) moves 250,000.

collections.deque is quick at both ends. append(x) and popleft() are O(1), and so are appendleft(x) and pop(). q[0] looks at the front. Inside, it keeps the items in blocks linked together, so taking the front moves nothing. In exchange, q[i] in the middle is O(n), but a queue only needs the ends.

A stack takes the newest; a queue takes the oldest. The stacks lesson kept a stack’s top at the end of a list, which is quick. A queue needs both ends, so it needs a deque. Two stacks can make a queue too: that’s the second practice problem.

Queues fit whenever the oldest item is the next to deal with: the requests in a time window, people in a line, jobs for a worker, and messages kept in order. A breadth-first search also keeps the places to visit next in a queue. It finds the shortest path through a maze.

Watch it, with a window of 100 ms, so the numbers stay short. The panel shows the queue, oldest on the left. Try your own times, like 99, 99, 100, 100 with a limit of 2: the burst at the edge of a window.

A queue of the requests in the window

10
21
32
1003
1014
1025

Work so far

window now	not started
queue, oldest on the left	empty
items moved	0

Step 1 of 10. A request goes through if fewer than 3 requests went through in the last 100 ms. The queue keeps the ones that did, oldest first.

Speed Ask me first Show as text

1from collections import deque
2 
4def allow(times: list[int], limit: int, window: int) -> list[bool]:
5    recent = deque()  # the requests that went through in the last window, oldest first
6    out = []
7    for t in times:
8        while recent and recent[0] <= t - window:
9            recent.popleft()  # the oldest has left the window
10        if len(recent) < limit:
11            recent.append(t)
12            out.append(True)
13        else:
14            out.append(False)
15    return out

Climb the ladder

All three give [True, True, True, False, True, True] for the example. What changes is how much they count or move.

The idea: Keep every request that went through in a list. For a new one, count how many are after t − window. If fewer than limit, it goes through.

It’s the rule, word for word, so it’s easy to trust.

def allow(times: list[int], limit: int, window: int) -> list[bool]:
    kept = []  # every request that went through
    out = []
    for t in times:
        recent = sum(1 for s in kept if s > t - window)  # the ones in the last window
        if recent < limit:
            kept.append(t)
            out.append(True)
        else:
            out.append(False)
    return out

Time: O(n²)
Space: O(n)
Why: Each request counts every one kept so far: up to n each, about n²/2 checks when most go through.

Where it breaks: the list only grows. 200,000 requests, 1 a millisecond, with 50 allowed per 100 ms: 100,000 go through, and each request counts all of them so far. That’s about 10 billion checks. It runs out of time.

The idea: Keep only the requests in the window, oldest first. Before each request, pop(0) every one at or before t − window. If fewer than limit are left, it goes through and joins the back.

The waste in Okay: it keeps and counts requests long gone from the window. The oldest leave first, so keep a queue and drop them from the front.

With a list, pop(0) moves the whole queue

10
21
32
43
1014
1025

Work so far

window now	not started
queue, oldest on the left	empty
items moved	0

Step 1 of 10. A request goes through if fewer than 4 requests went through in the last 100 ms. The queue keeps the ones that did, oldest first.

Speed Ask me first Show as text

1def allow(times: list[int], limit: int, window: int) -> list[bool]:
2    recent = []  # the requests that went through in the last window, oldest first
3    out = []
4    for t in times:
5        while recent and recent[0] <= t - window:
6            recent.pop(0)  # the oldest has left the window
7        if len(recent) < limit:
8            recent.append(t)
9            out.append(True)
10        else:
11            out.append(False)
12    return out

Highlighted lines are new in this rung.

def allow(times: list[int], limit: int, window: int) -> list[bool]:
    recent = []  # the requests that went through in the last window, oldest first
    out = []
    for t in times:
        while recent and recent[0] <= t - window:
            recent.pop(0)  # the oldest has left the window
        if len(recent) < limit:
            recent.append(t)
            out.append(True)
        else:
            out.append(False)
    return out

Time: O(n · L)was O(n²)
Space: O(L)was O(n)
Why: Each request is read once, but pop(0) moves every item behind the front. With up to L in the window, each pop moves up to L: O(n · L).

What changed from the previous rung

def allow(times: list[int], limit: int, window: int) -> list[bool]:
    kept = []  # every request that went through
    recent = []  # the requests that went through in the last window, oldest first
    out = []
    for t in times:
        recent = sum(1 for s in kept if s > t - window)  # the ones in the last window
        if recent < limit:
            kept.append(t)
        while recent and recent[0] <= t - window:
            recent.pop(0)  # the oldest has left the window
        if len(recent) < limit:
            recent.append(t)
            out.append(True)
        else:
            out.append(False)
    return out

Where it breaks: a big window. 600,000 requests, with 250,000 allowed per 300,000 ms, keep up to 250,000 in the list, and each pop(0) moves them all: about 60 billion moves. It runs out of time on the big speed test, though a small window is quick.

The idea: The same, with a collections.deque: popleft() takes the front without moving anything.

The waste in Better: a list is only quick at its end. A deque is quick at both, so the front costs nothing.

Highlighted lines are new in this rung.

from collections import deque


def allow(times: list[int], limit: int, window: int) -> list[bool]:
    recent = deque()  # the requests that went through in the last window, oldest first
    out = []
    for t in times:
        while recent and recent[0] <= t - window:
            recent.popleft()  # the oldest has left the window
        if len(recent) < limit:
            recent.append(t)
            out.append(True)
        else:
            out.append(False)
    return out

Time: O(n)was O(n · L)
Space: O(L)
Why: Each request joins once and leaves at most once, and append() and popleft() are O(1): O(n) in all. The deque holds at most limit requests.

What changed from the previous rung

from collections import deque


def allow(times: list[int], limit: int, window: int) -> list[bool]:
    recent = []  # the requests that went through in the last window, oldest first
    recent = deque()  # the requests that went through in the last window, oldest first
    out = []
    for t in times:
        while recent and recent[0] <= t - window:
            recent.pop(0)  # the oldest has left the window
            recent.popleft()  # the oldest has left the window
        if len(recent) < limit:
            recent.append(t)
            out.append(True)
        else:
            out.append(False)
    return out

When Best isn’t best: many users at once. One deque per user holds up to limit times each, which is a lot of memory for a big limit. Real limiters often keep just two counts per user: one for this clock window and one for the window before. They weight the one before by how much of it is still in the last window ms. It’s close enough, in O(1) memory.

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 small window. Better passes that one, but runs out of time on the big one.

Limit the requests

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: allow([1, 2, 3, 4], 3, 1000) → [True, True, True, False]
Not run yet: allow([1, 2, 3, 1000, 1001, 1002], 3, 1000) → [True, True, True, False, True, True]
Not run yet: allow([999, 999, 1000, 1000], 2, 1000): the burst at the edge of a second → [True, True, False, False]
Not run yet: allow([0, 1, 2, 500, 1000, 1001], 3, 1000): a request turned away doesn’t count → [True, True, True, False, True, True]
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 200,000 requests, 1 a millisecond, 50 allowed per 100 ms
Not run yet: Speed test: 600,000 requests, 1 a millisecond, 250,000 allowed per 300,000 ms

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

Try your own input

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: count every request kept	O(n²)	O(n)	It’s the rule, word for word	Counts requests long gone from the window	A few requests, checked by hand
Better: a list, with `pop(0)`	O(n · L), for up to L in the window	O(L)	Keeps only the window	`pop(0)` moves every item behind the front: O(n²) for a big window	A small window
Best: a deque	O(n)	O(L)	Nothing moves	One deque per user is a lot of memory for many users	Always, for a queue in Python

How much work is that? Each bar is one rung. There are n requests, 1 a millisecond, with a window and a limit of n/2. So every request goes through and the window is always full. Pick a size, or run the race.

Checking n requests with the window full

OkayCount every request kept · O(n²)≈ 180,000,000,000 requests counted
BetterA list, with pop(0) · O(n · L)≈ 90,000,000,000 items moved
BestA deque · O(n)≈ 1,200,000 steps

At n = 600,000, Okay does about 150,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.

Okay counts twice as much as Better moves, and both grow as n². Best appends each request once and pops it at most once: about 2n steps.

The race gives every step the same time, but real steps differ. Each of Okay’s checks is a step of Python, while pop(0) moves its items in C, many at a time. In this page’s Python, 10,000 requests with 5,000 in the window take Okay a few seconds. Twice as many take it about 4 times as long. Better and Best both take a few hundredths of a second or less, so they look the same. The gap shows with more: try 100,000 requests with 50,000 in the window. Better takes from a quarter of a second to a few seconds, depending on the computer. Best takes a few hundredths.

Common mistakes and edge cases

Count only what went through. A request turned away isn’t added, so it doesn’t use up the limit. Add it, and a client that keeps trying is locked out for ever.
Mind the edge of the window. With a window of 1,000 ms, the request at 1 ms has left by 1,001 ms: <= takes it off. Pick <= or < on purpose and test the edge, or one too many goes through, or one too few.
A deque isn’t a list. q[i] in the middle is O(n), and a slice like q[1:3] raises TypeError. A queue only needs the ends.
deque(maxlen=k) drops from the front by itself. That’s right for the last k items. Here the window is a time, not a count, so pop the old ones yourself.

Say it in the interview

Questions to ask first

Is the limit per user, or for everyone at once?
Does a request that’s turned away count against the limit?
How big can the limit and the window be, and how many users are there? That decides the memory.

A 60-second walkthrough

“I’ll keep a queue of the times of the requests that went through, oldest first, in a collections.deque. For each request at time t, I pop from the front every time at or before t minus the window, because those have left. If fewer than limit are left, the request goes through, and I append its time. Requests come in order, so the oldest always leave first. Each time is appended once and popped at most once, so it’s O(n) for n requests, and the queue holds at most limit times. I use a deque, not a list, because pop(0) on a list moves every other item.”

Likely follow-ups

Many users? A dict from each user to their own deque. Drop the users who were quiet for a whole window, or the dict only grows.
Less memory? Two counts per user: one for this clock window and one for the window before. Weight the one before by how much of it is still in the window. Or a token bucket: tokens come back at a steady rate, and each request spends one.
Requests out of order? Then the oldest isn’t always at the front. Sort them first, or keep the times sorted as they come.
Several servers? Keep the counts in one shared store, like Redis, so every server sees the same window.

Practice

Three problems, from easy to medium: a line for tickets, a queue made of two stacks, and the first user who has sent just one message. 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. Buying tickets in a line (easy)

Write wait_time(tickets, k). People stand in a line, and person i wants tickets[i] tickets. Each second, the person at the front buys one. If they want more, they go to the back of the line. If not, they leave. Return how many seconds it takes until person k, counting from 0, has all of theirs.

Example: wait_time([2, 3, 2], 2) is 6. They buy in the order 0, 1, 2, 0, 1, 2, so person 2 gets their second ticket in second 6.

Hint 1 of 3

Act it out with a queue of people: take the one at the front, sell them a ticket, and put them at the back if they want more.

Hint 2 of 3

Each second sells one ticket, so the answer is how many tickets are sold until person k is done. How many does each person buy by then?

Hint 3 of 3

Someone up to k buys min(their tickets, tickets[k]). Someone behind k gets one turn fewer: min(their tickets, tickets[k] − 1).

Buying tickets in a line

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: wait_time([2, 3, 2], 2) → 6
Not run yet: wait_time([5, 1, 1, 1], 0) → 8
Not run yet: wait_time([3, 3, 3], 1): the person behind k gets one turn fewer → 8
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 200,000 people who want 3 each, and k is the last → 600000
Not run yet: Speed test: 1,000 people who want a million each → 1000000000

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

Try your own input

Show the Okay, Better and Best answers

The idea: Keep the line as a list of people. Each second, pop(0) the front person, sell them a ticket, and append them if they want more. Stop when person k has all of theirs.

It does just what the line does, one ticket at a time.

def wait_time(tickets: list[int], k: int) -> int:
    line = list(range(len(tickets)))  # each person, by their place at the start
    left = list(tickets)
    seconds = 0
    while True:
        i = line.pop(0)  # the person at the front buys one ticket
        left[i] -= 1
        seconds += 1
        if left[i] > 0:
            line.append(i)  # to the back, for the next one
        elif i == k:
            return seconds

Time: O(T · n)
Space: O(n)
Why: For each of the T tickets sold, pop(0) moves the rest of the line: up to n people each time.

Where it breaks: 200,000 people who want 3 each buy 600,000 tickets, and each pop(0) moves up to 200,000 people: about 100 billion moves. It runs out of time.

The idea: The same, with a deque: popleft() takes the front person without moving the line.

The waste in Okay: pop(0) moves the whole line every second. A deque takes the front in one step.

Highlighted lines are new in this rung.

from collections import deque


def wait_time(tickets: list[int], k: int) -> int:
    line = deque(range(len(tickets)))  # each person, by their place at the start
    left = list(tickets)
    seconds = 0
    while True:
        i = line.popleft()  # the person at the front buys one ticket
        left[i] -= 1
        seconds += 1
        if left[i] > 0:
            line.append(i)  # to the back, for the next one
        elif i == k:
            return seconds

Time: O(T)was O(T · n)
Space: O(n)
Why: Each second is O(1) now, but there’s one for every ticket sold, and T can be far bigger than n.

What changed from the previous rung

from collections import deque


def wait_time(tickets: list[int], k: int) -> int:
    line = list(range(len(tickets)))  # each person, by their place at the start
    line = deque(range(len(tickets)))  # each person, by their place at the start
    left = list(tickets)
    seconds = 0
    while True:
        i = line.pop(0)  # the person at the front buys one ticket
        i = line.popleft()  # the person at the front buys one ticket
        left[i] -= 1
        seconds += 1
        if left[i] > 0:
            line.append(i)  # to the back, for the next one
        elif i == k:
            return seconds

Where it breaks: big orders. 1,000 people who want a million each buy a billion tickets: a billion turns. It runs out of time.

The idea: Someone up to k buys until k is done, or until they are: min(t, tickets[k]). Someone behind k gets one turn fewer: min(t, tickets[k] − 1). Add them up.

The waste in Better: it sells every ticket, one at a time, just to count them. You only need how many each person buys before k is done.

Highlighted lines are new in this rung.

def wait_time(tickets: list[int], k: int) -> int:
    want = tickets[k]
    seconds = 0
    for i, t in enumerate(tickets):
        if i <= k:
            seconds += min(t, want)  # buys until k is done, or until they are
        else:
            seconds += min(t, want - 1)  # behind k: one turn fewer
    return seconds

Time: O(n)was O(T)
Space: O(1)was O(n)
Why: One pass over the line, and nothing is acted out.

What changed from the previous rung

from collections import deque


def wait_time(tickets: list[int], k: int) -> int:
    line = deque(range(len(tickets)))  # each person, by their place at the start
    left = list(tickets)
    want = tickets[k]
    seconds = 0
    while True:
        i = line.popleft()  # the person at the front buys one ticket
        left[i] -= 1
        seconds += 1
        if left[i] > 0:
            line.append(i)  # to the back, for the next one
        elif i == k:
            return seconds
    for i, t in enumerate(tickets):
        if i <= k:
            seconds += min(t, want)  # buys until k is done, or until they are
        else:
            seconds += min(t, want - 1)  # behind k: one turn fewer
    return seconds

When Best isn’t best: it gives one person’s time. For the order everyone leaves in, act it out with a deque, or sort the people by how many they want, then by their place.

2. A queue made of two stacks (easy)

Write run(ops). Each op is either a whole number, 0 or more, which joins the back of the queue, or -1, which takes the front one off. Return the numbers taken, in order. The hard part: use lists only as stacks, with append(), pop() from the end, [-1] and len(). No pop(0), and no deque. There’s always something to take.

Example: run([1, 2, -1, 3, -1, -1]) is [1, 2, 3].

Hint 1 of 3

Pour one stack into another, and the order flips: the oldest ends up on top.

Hint 2 of 3

Keep two stacks: an inbox, where new numbers go, and an outbox, to take from. When the outbox is empty, pour the whole inbox into it.

Hint 3 of 3

Never pour back. The outbox holds the oldest numbers in order. New ones wait in the inbox until the outbox runs out.

A queue made of two stacks

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: run([1, 2, 3, -1, -1, -1]) → [1, 2, 3]
Not run yet: run([1, 2, -1, 3, -1, -1]): 3 joins after a take, and still comes after 2 → [1, 2, 3]
Not run yet: run([5, -1, 6, -1]) → [5, 6]
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 100,000 numbers join, then all are taken
Not run yet: Speed test: 100,000 numbers join, then one joins and one is taken, 100,000 times

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

Try your own input

Show the Okay, Better and Best answers

The idea: New numbers go on the inbox. To take one, pour the inbox into the outbox, so the oldest is on top, pop it, and pour the rest back.

Between ops, every number is in the inbox, so it’s easy to follow.

def run(ops: list[int]) -> list[int]:
    inbox, outbox = [], []
    taken = []
    for op in ops:
        if op >= 0:
            inbox.append(op)
        else:
            while inbox:
                outbox.append(inbox.pop())  # pour: the oldest ends up on top
            taken.append(outbox.pop())
            while outbox:
                inbox.append(outbox.pop())  # pour it all back
    return taken

Time: O(n²)
Space: O(n)
Why: Each take pours every number across and back: up to 2n moves, for each of up to n takes.

Where it breaks: 100,000 numbers, then 100,000 takes. Each take pours what’s left twice: about 10 billion moves. It runs out of time.

The idea: Keep every number in one of the two stacks. Before adding, pour the outbox back into the inbox, if it holds any. Before taking, pour the inbox into the outbox.

The waste in Okay: it pours back after every take, even when the next op takes again.

Highlighted lines are new in this rung.

def run(ops: list[int]) -> list[int]:
    inbox, outbox = [], []  # every item is in one of the two
    taken = []
    for op in ops:
        if op >= 0:
            while outbox:
                inbox.append(outbox.pop())  # adding again: pour it all back
            inbox.append(op)
        else:
            while inbox:
                outbox.append(inbox.pop())  # taking again: the oldest ends up on top
            taken.append(outbox.pop())
    return taken

Time: O(n²)
Space: O(n)
Why: A run of takes pours once, but each switch from adding to taking, or back, pours every number: O(n) per switch.

What changed from the previous rung

def run(ops: list[int]) -> list[int]:
    inbox, outbox = [], []
    inbox, outbox = [], []  # every item is in one of the two
    taken = []
    for op in ops:
        if op >= 0:
            while outbox:
                inbox.append(outbox.pop())  # adding again: pour it all back
            inbox.append(op)
        else:
            while inbox:
                outbox.append(inbox.pop())  # pour: the oldest ends up on top
                outbox.append(inbox.pop())  # taking again: the oldest ends up on top
            taken.append(outbox.pop())
            while outbox:
                inbox.append(outbox.pop())  # pour it all back
    return taken

Where it breaks: switching. After 100,000 numbers join, one joins and one is taken, 100,000 times. Every op is a switch, and each pours about 100,000 numbers: about 20 billion moves. It runs out of time.

The idea: New numbers go on the inbox. To take one, pop the outbox. Only when the outbox is empty, pour the whole inbox into it first. Never pour back.

The waste in Better: pouring back undoes the order it just built. The outbox already holds the oldest numbers, oldest on top: take from it until it’s empty.

Highlighted lines are new in this rung.

def run(ops: list[int]) -> list[int]:
    inbox, outbox = [], []  # outbox holds the oldest items, the oldest on top
    taken = []
    for op in ops:
        if op >= 0:
            inbox.append(op)
        else:
            if not outbox:
                while inbox:
                    outbox.append(inbox.pop())  # pour only when outbox is empty
            taken.append(outbox.pop())
    return taken

Time: O(n)was O(n²)
Space: O(n)
Why: Each number is pushed once, poured once and popped once: O(1) on average per op, though one take can pour n. That’s called amortized O(1).

What changed from the previous rung

def run(ops: list[int]) -> list[int]:
    inbox, outbox = [], []  # every item is in one of the two
    inbox, outbox = [], []  # outbox holds the oldest items, the oldest on top
    taken = []
    for op in ops:
        if op >= 0:
            while outbox:
                inbox.append(outbox.pop())  # adding again: pour it all back
            inbox.append(op)
        else:
            while inbox:
                outbox.append(inbox.pop())  # taking again: the oldest ends up on top
            if not outbox:
                while inbox:
                    outbox.append(inbox.pop())  # pour only when outbox is empty
            taken.append(outbox.pop())
    return taken

When Best isn’t best: one take can still pour every number, a pause a real-time system may not allow. In Python, a deque has no such pause, and it’s simpler.

3. The first user who sent just one message (medium)

Write first_unique(ids). ids[i] is the user who sent message i. After each message, find the users who have sent exactly one message so far, and say which of them sent theirs first. Return those answers, with -1 when there’s none.

Example: first_unique([4, 7, 4, 9, 7]) is [4, 4, 7, 7, 9]. After the second 4, user 7 is the first with one message. After the second 7, it’s user 9.

Hint 1 of 3

Count each user’s messages as they come, in a dict.

Hint 2 of 3

The answer is the oldest user with a count of 1. Keep the users who sent one message in a queue, oldest first.

Hint 3 of 3

A user who sends again never has a count of 1 again. So when the front of the queue has sent again, popleft() them: each user leaves at most once.

The first user who sent just one message

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: first_unique([4, 7, 4, 9, 7]) → [4, 4, 7, 7, 9]
Not run yet: first_unique([2, 2]) → [2, -1]
Not run yet: first_unique([5, 6, 5, 5, 7]): a third message from 5 doesn’t bring it back → [5, 5, 6, 6, 6]
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 100,000 users, one message each
Not run yet: Speed test: 50,000 users send two messages each, then 50,000 new users send one

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

Try your own input

Show the Okay, Better and Best answers

The idea: After each message, count every user’s messages so far. Then read the messages from the first, and stop at the first user with a count of 1.

Each answer comes straight from the messages so far, so it’s easy to check.

def first_unique(ids: list[int]) -> list[int]:
    out = []
    for i in range(len(ids)):
        counts = {}
        for x in ids[: i + 1]:  # count again, from the first message
            counts[x] = counts.get(x, 0) + 1
        answer = -1
        for x in ids[: i + 1]:
            if counts[x] == 1:
                answer = x
                break
        out.append(answer)
    return out

Time: O(n²)
Space: O(n)
Why: After message i, it reads all i messages twice: about n² reads in all.

Where it breaks: 100,000 messages. Each answer reads every message before it, twice: about 10 billion reads. It runs out of time.

The idea: Keep each user’s count in a dict as messages come, and a list of users in the order they first sent. For each answer, read the list from the start, and stop at the first user with a count of 1.

The waste in Okay: it counts every message again after each new one. A dict keeps the counts up to date as they come.

Highlighted lines are new in this rung.

def first_unique(ids: list[int]) -> list[int]:
    counts = {}
    order = []  # each id once, by its first message
    out = []
    for x in ids:
        if x not in counts:
            order.append(x)
        counts[x] = counts.get(x, 0) + 1
        answer = -1
        for y in order:  # from the oldest: the first one sent only once
            if counts[y] == 1:
                answer = y
                break
        out.append(answer)
    return out

Time: O(n · u)was O(n²)
Space: O(u)was O(n)
Why: The counts cost O(1) a message, but each answer reads past every user at the front who sent again: up to u users, for u users in all.

What changed from the previous rung

def first_unique(ids: list[int]) -> list[int]:
    counts = {}
    order = []  # each id once, by its first message
    out = []
    for i in range(len(ids)):
        counts = {}
        for x in ids[: i + 1]:  # count again, from the first message
            counts[x] = counts.get(x, 0) + 1
    for x in ids:
        if x not in counts:
            order.append(x)
        counts[x] = counts.get(x, 0) + 1
        answer = -1
        for x in ids[: i + 1]:
            if counts[x] == 1:
                answer = x
        for y in order:  # from the oldest: the first one sent only once
            if counts[y] == 1:
                answer = y
                break
        out.append(answer)
    return out

Where it breaks: users who sent again stay at the front of the list. With 50,000 of them, each of the next 50,000 messages reads past them all: 2.5 billion reads. It runs out of time.

The idea: Keep the counts in a dict. When a user sends their first message, append them to a deque. For each answer, popleft() while the front user has sent again, then the front is the answer.

The waste in Better: it reads past the users who sent again, every time. They never come back, so take them off the front.

Highlighted lines are new in this rung.

from collections import deque


def first_unique(ids: list[int]) -> list[int]:
    counts = {}
    waiting = deque()  # ids that were sent once, oldest first
    out = []
    for x in ids:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] == 1:
            waiting.append(x)
        while waiting and counts[waiting[0]] > 1:
            waiting.popleft()  # sent again, so never the answer again
        out.append(waiting[0] if waiting else -1)
    return out

Time: O(n)was O(n · u)
Space: O(u)
Why: Each user joins the deque once and leaves at most once, so all the popleft() calls add up to u at most: O(1) on average per message.

What changed from the previous rung

from collections import deque


def first_unique(ids: list[int]) -> list[int]:
    counts = {}
    order = []  # each id once, by its first message
    waiting = deque()  # ids that were sent once, oldest first
    out = []
    for x in ids:
        if x not in counts:
            order.append(x)
        counts[x] = counts.get(x, 0) + 1
        answer = -1
        for y in order:  # from the oldest: the first one sent only once
            if counts[y] == 1:
                answer = y
                break
        out.append(answer)
        if counts[x] == 1:
            waiting.append(x)
        while waiting and counts[waiting[0]] > 1:
            waiting.popleft()  # sent again, so never the answer again
        out.append(waiting[0] if waiting else -1)
    return out

When Best isn’t best: the deque keeps a user who sent again until they reach the front. An OrderedDict of just the users with one message drops them at once: delete a user when they send again, and its first key is the answer. That’s O(1) per message too.

Check yourself

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

Predict the outputWhat does this print?

from collections import deque

q = deque()
for x in [1, 2, 3]:
    q.append(x)
q.popleft()
print(q[0])

123IndexError

Multiple choiceA limit of 100 requests a second counts the requests in each clock second, t // 1000. How many can a client get through from 999 ms to 1,000 ms?
100101200Nothing past the limit

Spot the bugThis limits requests with a queue. What's wrong?

from collections import deque

def allow(times, limit, window):
    recent = deque()
    out = []
    for t in times:
        while recent and recent[0] <= t - window:
            recent.popleft()
        recent.append(t)
        out.append(len(recent) <= limit)
    return out

A request turned away still joins the queue, so it uses up the limitIt's O(n²)recent[0] raises IndexError when the queue is emptyNothing

Multiple choiceA queue of 10,000 items is kept in a list. Each item is taken with pop(0) until the list is empty. About how many times does an item move one place?
About 10,000About 20,000About 50 millionNever
Pick the patternJobs come in all day, and one worker takes them in the order they came. Which fits best for the jobs waiting?
A collections.deque, with append() and popleft()A list, with append() and pop()A setA list, sorted after each new job

Flashcards

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

Cheat sheet

A queue is first in, first out: append at the back, take from the front.
In Python: from collections import deque, then q.append(x), q.popleft(), q[0] and not q. Each is O(1).
Not a list’s pop(0) or insert(0, x): they move every other item, O(n).
A window in time is a queue: before each new item, pop the ones that have left from the front.
Count only what you keep: a request turned away doesn’t use up the limit.
Two stacks make a queue: pour the inbox into the outbox only when the outbox is empty. That’s O(1) on average.
A queue can drop items late: pop the ones that no longer count when they reach the front.
deque(maxlen=k) keeps the last k items, and drops from the front by itself.

Go deeper

In the Python docs: collections.deque, and Using lists as queues.
Step through more: Rate limiter on the DSA visualizer, with a deque and with a list.
Breadth-first search on the DSA visualizer takes from the front of a queue to find the shortest path through a maze.
The stacks lesson checks brackets with a stack, the queue’s cousin.
Next on the DSA roadmap: two pointers.

Can you do these now?

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

Say what first in, first out means, and spot a problem that needs it
Use collections.deque as a queue, with append() and popleft()
Keep the requests of the last window in a queue, to limit a rate
Build a queue from two stacks, and say why it’s O(1) per item on average

Status: Not started

My rate limiter let 200 requests through in one second

See the problem

Define the task

Pause and think

Understand the idea

Climb the ladder

Keep every request, and count the recent ones

A queue in a list, taken from with pop(0)

A queue in a deque

Write it yourself

Limit the requests

Compare

Common mistakes and edge cases

Say it in the interview

Practice

1. Buying tickets in a line (easy)

Buying tickets in a line

Act it out, with a list

Act it out, with a deque

Count each person’s tickets

2. A queue made of two stacks (easy)

A queue made of two stacks

Pour it all over and back for each take

Pour only when you switch

Pour only when the outbox is empty

3. The first user who sent just one message (medium)

The first user who sent just one message

Count again after each message

Keep the counts, and look from the oldest user

A queue of the users with one message

Check yourself

Flashcards

Cheat sheet

Go deeper

Can you do these now?