What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Advanced Data Structures

Builds on Lower Bound and Upper Bound, which you haven’t finished yet.

P3MediumMental model~3 min speedrun

Ordered Set (Floor/Ceiling Lookups)

The problem

My Calendar I (LC 729)(opens leetcode.com)

Build a calendar, MyCalendar, that takes events one at a time and keeps only those that fit.

An event is a half-open range of time [startTime, endTime): it covers every moment x with startTime <= x < endTime. Two events double book when some moment belongs to both. So an event that ends at 20 and one that starts at 20 share no moment and do not double book.

MyCalendar() creates an empty calendar.
boolean book(int startTime, int endTime) adds the event and returns true when it double books with no event already in the calendar. Otherwise it returns false and the calendar stays as it was.

Example 1

Input:["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]]

Output:[null, true, false, true]

[10, 20) is stored. [15, 25) shares moments 15 to 19 with it, so it is rejected. [20, 30) starts exactly where [10, 20) stops, so they share no moment and it is stored.

Ordered Set

sorted keys ➔ bisect position ➔ floor and ceiling neighbours

Spot it when: You insert keys in any order and, between inserts, need the closest stored key at or below a value (the floor) or above it (the ceiling), as in My Calendar I (LC 729).

Ordered Set

Python

1	import bisect
2
3
4	class MyCalendar:
5	"""My Calendar I: keep booked events sorted by start; a new event can only clash with its two neighbours.
6	Time: O(log N) search + O(N) insert per book, N = bookings so far \| Space: O(N)
7	"""
8	def __init__(self) -> None:
9	self.starts: list[int] = [] # Start times of booked events, kept sorted
10	self.ends: list[int] = [] # ends[j] is the end of the event that starts at starts[j]
11
12	def book(self, startTime: int, endTime: int) -> bool:
13	i = bisect.bisect_right(self.starts, startTime) # Events before i start at or before startTime
14
15	# 1. Reject An Overlap With Either Neighbour, Else Insert Between Them:
16	# The floor and ceiling are the only stored events that could possibly overlap the new one,
17	# since every other event sits sorted further away; both half-open checks must stay strict.
18	if i > 0 and self.ends[i - 1] > startTime:
19	return False # Floor neighbour is still running at startTime
20	if i < len(self.starts) and self.starts[i] < endTime:
21	return False # Ceiling neighbour starts before endTime
22	self.starts.insert(i, startTime) # Insert in place: starts stays sorted
23	self.ends.insert(i, endTime)
24	return True

Invariant: starts holds every stored key in sorted order however the inserts arrive, so i = bisect.bisect_right(self.starts, startTime) puts the floor at i - 1 and the ceiling at i.

Keep the stored keys sorted however they arrive, so one bisect_right finds both neighbours of a new value: the floor at i - 1 and the ceiling at i. For a calendar that is all you need: stored events never overlap, so sorted by start they are sorted by end too, and every other event either ends before the floor starts or starts after the ceiling. A new event fits exactly when the floor has ended by startTime and the ceiling starts no earlier than endTime; then it is inserted at i in both starts and ends. The trap is the half-open ends: the checks are self.ends[i - 1] > startTime and self.starts[i] < endTime, strict, because an event ending at 20 and one starting at 20 share no moment.

See it run

An ordered list of starts: floor and ceiling checks

book -i -last result -

Each column is one slot of the sorted lists. The top row is starts, and the bottom row is ends. An empty cell is a slot not used yet.

floor the stored event at or before the new start
ceiling the stored event after the new start
new the event just inserted

No event is booked yet, so starts and ends are empty. Each book call finds its two neighbours with one bisect_right.

starts

ends

1 / 14

Gotchas1 of 5

The trap
Gotcha 1: Writing >= instead of > in the floor check
Mistake
```
if i > 0 and self.ends[i - 1] >= startTime:
```
Fix
```
if i > 0 and self.ends[i - 1] > startTime:
```
What happens: Events are half-open, so [10, 20) and [20, 30) share no moment. With >=, an event that ends at 20 blocks one that starts at 20. The ceiling check self.starts[i] < endTime must stay strict for the same reason.
Example: book(10, 20), then book(20, 30)
Mistake: returns FalseFix: returns True
Gotcha 2: Checking only the floor neighbour
Mistake
```
self.starts.insert(i, startTime)
```
Fix
```
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
```
What happens: The floor is the stored event that starts at or before startTime. It can't see an event that starts inside the new one. After book(10, 20), the new event [5, 11) has no floor. Its ceiling [10, 20) starts before 11, so only the ceiling check rejects it. Checking only the ceiling fails the other way. It misses an event that is still running at startTime.
Example: book(10, 20), then book(5, 11)
Mistake: returns TrueFix: returns False
Gotcha 3: Appending to self.ends instead of inserting at i
Mistake
```
self.ends.append(endTime)
```
Fix
```
self.ends.insert(i, endTime)
```
What happens: self.ends[j] must be the end of the event that starts at self.starts[j]. append puts the end in the last slot, while the start went to slot i. The two lists then pair the wrong starts and ends, and later checks read the wrong end.
Example: book(10, 20), book(0, 5), then book(5, 10)
Mistake: returns FalseFix: returns True

Gotcha 4: Inserting the event before both checks pass

Mistake

self.starts.insert(i, startTime)
self.ends.insert(i, endTime)
if i > 0 and self.ends[i - 1] > startTime:
    return False

Fix

if i > 0 and self.ends[i - 1] > startTime:
    return False
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
self.ends.insert(i, endTime)

What happens: A rejected event must leave no trace. If it is inserted first and then rejected, it stays in self.starts and self.ends. Later events that overlap only the rejected one are then rejected too.

Example: book(10, 20), book(15, 25), then book(20, 30)

Mistake: returns FalseFix: returns True

Gotcha 5: Expecting list.insert to take O(log N) time
What happens: bisect_right finds i in O(log N) time, but list.insert shifts every later entry. So one book costs O(N) time. My Calendar I (LC 729) allows at most 1000 calls, so the list is fast enough there. For many more bookings, use a balanced tree with the same floor and ceiling logic. Examples are Java's TreeMap, C++'s std::map and Python's sortedcontainers.SortedList.

Not this one if…

The keys arrive already sorted, as the timestamps in Time Based Key-Value Store (LC 981) do: appending keeps the list in order, so a binary search for the last stored key at or below the query is enough and nothing is ever inserted in the middle. See Upper Bound
The question is how many intervals overlap at the busiest moment, as in Meeting Rooms II (LC 253): every event matters at once, not which single stored key sits closest to one new point. See Sweep Line

Deep Dive

One search gives both neighbours

starts stays sorted after every insert. i = bisect.bisect_right(self.starts, startTime) returns the first index whose value is greater than startTime. So every value at index i - 1 or below is at most startTime, and every value at index i or above is greater.

The value at i - 1 is the floor: the largest stored start that is at most startTime. The value at i is the ceiling: the smallest stored start that is greater than startTime. One search, which takes O(log N) time, finds both.

Example: starts = [10, 20] and book(15, 25). The search returns i = 1. The floor is starts[0] = 10, and the ceiling is starts[1] = 20.

Why only the floor and the ceiling can overlap

The calendar holds no overlaps. So when the events are sorted by start, each event ends before the next one starts: ends[j] <= starts[j + 1]. The events are sorted by end too.

Take an event before the floor. It ends no later than the floor starts, and the floor starts at or before startTime. So it ends before the new event starts, and it cannot overlap.

Take an event after the ceiling. It starts no earlier than the ceiling ends, and the ceiling ends after it starts. If the ceiling starts at or after endTime, then so does every later event. So the new event overlaps nothing.

This leaves two checks. The floor must end by startTime, which is self.ends[i - 1] <= startTime. The ceiling must start no earlier than endTime, which is self.starts[i] >= endTime. For the five calls book(10, 20), book(15, 25), book(20, 30), book(5, 10) and book(25, 35), the results are true, false, true, true and false.

Half-open ends: both comparisons are strict

An event [10, 20) includes 10 and excludes 20. The event [20, 30) starts at 20. The two share no moment, so both can be booked.

In the code, a floor that ends at 20 and a new start of 20 must pass. The check self.ends[i - 1] > startTime is 20 > 20, which is false, so the booking continues. With >=, the check would be true and the booking would be rejected by mistake.

The same holds for the ceiling. book(5, 10) when starts = [10, 20]: the check self.starts[i] < endTime is 10 < 10, which is false, so the booking passes.

Equal starts are handled by bisect_right. After book(10, 20), the call book(10, 15) returns i = 1. The floor is [10, 20), and 20 > 10 rejects the booking.

Cost, and a faster structure

bisect_right takes O(log N) time. list.insert shifts every later entry, so it takes O(N) time. One book call costs O(N) time, and the space is O(N).

My Calendar I (LC 729) allows at most 1000 calls, so the lists are fast enough. For many more bookings, use a balanced search tree. Java's TreeMap offers floorKey and ceilingKey. The checks stay the same.

The same floor and ceiling idea solves Data Stream as Disjoint Intervals (LC 352): the new number is compared with the interval before it and the interval after it, and it merges with them when they touch.

Insert only after both checks pass. A rejected event that was inserted first would stay in starts and ends and wrongly block later events.

60-Second Pitch

"The calendar never holds overlapping events, so sorted by start it is also sorted by end. A new event can overlap only the stored event just before it or just after it. I keep starts and ends sorted. One bisect_right gives i. The floor is at i - 1, and the ceiling is at i. I reject the booking if the floor ends after startTime, or if the ceiling starts before endTime. Both comparisons are strict, because the events are half-open. Otherwise I insert at i in both lists. The search is O(log N) and the insert is O(N), which is fine for 1000 calls. For more, I use a balanced tree with floor and ceiling lookups."

Common Questions

Why is it enough to check only two neighbours?: Stored events do not overlap, so sorted by start they are also sorted by end. Every event before the floor ends before the floor starts. Every event after the ceiling starts after the ceiling ends. If the new event clears the floor and the ceiling, it clears all of them.
Why bisect_right and not bisect_left?: bisect_right puts an event with an equal start before index i, so that event becomes the floor. Its end is greater than startTime, so the floor check rejects the booking. The floor and ceiling have a clear meaning: at most startTime, and greater than startTime.
How would you make the insert fast?: Use a balanced search tree or a skip list, which insert in O(log N) time and offer floor and ceiling lookups. Java's TreeMap has floorKey and ceilingKey. In Python, use a sorted container from a library when it is allowed. Plain lists are O(N) per insert.
What changes if events may overlap, as in My Calendar II (LC 731)?: Two neighbours are no longer enough, because several stored events can overlap the new one. A new event is rejected only when it overlaps a moment that two stored events already cover. Keep the booked events in one list and the intervals that two events cover in a second list, and check the new event against both lists.
Why keep ends as a second list?: The floor check needs the end of the floor event, ends[i - 1]. The two lists share one index, so the end of the event at starts[j] is ends[j]. Both inserts use the same index i.

SWE Reasoning

Spot it

Keys arrive in any order, and between inserts a question asks for the closest stored key at or below a value, or above it.
A new item can conflict only with its nearest neighbours, because the stored items never conflict with each other.
The structure must stay sorted. Sorting again for every query costs O(N log N) time each.
The intervals are half-open, [start, end), so touching ends are allowed.

The invariant, step by step

starts is sorted, and ends[j] is the end of the event that starts at starts[j].
i = bisect.bisect_right(self.starts, startTime) splits starts into values at most startTime and values greater than startTime.
The floor is at i - 1. If self.ends[i - 1] > startTime, the floor event is still running at startTime, and the function returns False.
The ceiling is at i. If self.starts[i] < endTime, the ceiling event starts before the new event ends, and the function returns False.
Stored events do not overlap, so no other stored event can overlap the new one.
Both checks passed, so the function inserts startTime into starts and endTime into ends at the same index i. Both lists stay sorted and aligned.

Traps

>= in the floor check. An event that ends at 20 then blocks one that starts at 20. book(10, 20) followed by book(20, 30) returns False and should return True. The ceiling check < must stay strict for the same reason.
Only one neighbour. For book(10, 20) followed by book(5, 11), there is no floor, and only the ceiling check rejects it. Checking only the floor returns True.
append for ends. ends[j] must pair with starts[j]. append puts the end in the last slot while the start went to index i, so later checks read the wrong end.
Insert before the checks. A rejected event that stays in the lists blocks later events that overlap only the rejected one.
Assuming O(log N) insert. list.insert is O(N). Say this in an interview, and name a balanced tree as the fix.

Practice

Canonical LeetCode:My Calendar I (LC 729)Data Stream as Disjoint Intervals (LC 352)Range Module (LC 715)

Theory Context•Advanced Data Structures

Builds on Lower Bound and Upper Bound, which you haven’t finished yet.

P3MediumMental model~3 min speedrun

Ordered Set (Floor/Ceiling Lookups)

The problem

My Calendar I (LC 729)(opens leetcode.com)

Build a calendar, MyCalendar, that takes events one at a time and keeps only those that fit.

MyCalendar() creates an empty calendar.
boolean book(int startTime, int endTime) adds the event and returns true when it double books with no event already in the calendar. Otherwise it returns false and the calendar stays as it was.

Example 1

Input:["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]]

Output:[null, true, false, true]

[10, 20) is stored. [15, 25) shares moments 15 to 19 with it, so it is rejected. [20, 30) starts exactly where [10, 20) stops, so they share no moment and it is stored.

Ordered Set

sorted keys ➔ bisect position ➔ floor and ceiling neighbours

Spot it when: You insert keys in any order and, between inserts, need the closest stored key at or below a value (the floor) or above it (the ceiling), as in My Calendar I (LC 729).

Ordered Set

Python

1	import bisect
2
3
4	class MyCalendar:
5	"""My Calendar I: keep booked events sorted by start; a new event can only clash with its two neighbours.
6	Time: O(log N) search + O(N) insert per book, N = bookings so far \| Space: O(N)
7	"""
8	def __init__(self) -> None:
9	self.starts: list[int] = [] # Start times of booked events, kept sorted
10	self.ends: list[int] = [] # ends[j] is the end of the event that starts at starts[j]
11
12	def book(self, startTime: int, endTime: int) -> bool:
13	i = bisect.bisect_right(self.starts, startTime) # Events before i start at or before startTime
14
15	# 1. Reject An Overlap With Either Neighbour, Else Insert Between Them:
16	# The floor and ceiling are the only stored events that could possibly overlap the new one,
17	# since every other event sits sorted further away; both half-open checks must stay strict.
18	if i > 0 and self.ends[i - 1] > startTime:
19	return False # Floor neighbour is still running at startTime
20	if i < len(self.starts) and self.starts[i] < endTime:
21	return False # Ceiling neighbour starts before endTime
22	self.starts.insert(i, startTime) # Insert in place: starts stays sorted
23	self.ends.insert(i, endTime)
24	return True

Invariant: starts holds every stored key in sorted order however the inserts arrive, so i = bisect.bisect_right(self.starts, startTime) puts the floor at i - 1 and the ceiling at i.

See it run

An ordered list of starts: floor and ceiling checks

book -i -last result -

Each column is one slot of the sorted lists. The top row is starts, and the bottom row is ends. An empty cell is a slot not used yet.

floor the stored event at or before the new start
ceiling the stored event after the new start
new the event just inserted

No event is booked yet, so starts and ends are empty. Each book call finds its two neighbours with one bisect_right.

starts

ends

1 / 14

Gotchas1 of 5

The trap
Gotcha 1: Writing >= instead of > in the floor check
Mistake
```
if i > 0 and self.ends[i - 1] >= startTime:
```
Fix
```
if i > 0 and self.ends[i - 1] > startTime:
```
What happens: Events are half-open, so [10, 20) and [20, 30) share no moment. With >=, an event that ends at 20 blocks one that starts at 20. The ceiling check self.starts[i] < endTime must stay strict for the same reason.
Example: book(10, 20), then book(20, 30)
Mistake: returns FalseFix: returns True
Gotcha 2: Checking only the floor neighbour
Mistake
```
self.starts.insert(i, startTime)
```
Fix
```
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
```
What happens: The floor is the stored event that starts at or before startTime. It can't see an event that starts inside the new one. After book(10, 20), the new event [5, 11) has no floor. Its ceiling [10, 20) starts before 11, so only the ceiling check rejects it. Checking only the ceiling fails the other way. It misses an event that is still running at startTime.
Example: book(10, 20), then book(5, 11)
Mistake: returns TrueFix: returns False
Gotcha 3: Appending to self.ends instead of inserting at i
Mistake
```
self.ends.append(endTime)
```
Fix
```
self.ends.insert(i, endTime)
```
What happens: self.ends[j] must be the end of the event that starts at self.starts[j]. append puts the end in the last slot, while the start went to slot i. The two lists then pair the wrong starts and ends, and later checks read the wrong end.
Example: book(10, 20), book(0, 5), then book(5, 10)
Mistake: returns FalseFix: returns True

Gotcha 4: Inserting the event before both checks pass

Mistake

self.starts.insert(i, startTime)
self.ends.insert(i, endTime)
if i > 0 and self.ends[i - 1] > startTime:
    return False

Fix

if i > 0 and self.ends[i - 1] > startTime:
    return False
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
self.ends.insert(i, endTime)

Example: book(10, 20), book(15, 25), then book(20, 30)

Mistake: returns FalseFix: returns True

Gotcha 5: Expecting list.insert to take O(log N) time
What happens: bisect_right finds i in O(log N) time, but list.insert shifts every later entry. So one book costs O(N) time. My Calendar I (LC 729) allows at most 1000 calls, so the list is fast enough there. For many more bookings, use a balanced tree with the same floor and ceiling logic. Examples are Java's TreeMap, C++'s std::map and Python's sortedcontainers.SortedList.

Not this one if…

The keys arrive already sorted, as the timestamps in Time Based Key-Value Store (LC 981) do: appending keeps the list in order, so a binary search for the last stored key at or below the query is enough and nothing is ever inserted in the middle. See Upper Bound
The question is how many intervals overlap at the busiest moment, as in Meeting Rooms II (LC 253): every event matters at once, not which single stored key sits closest to one new point. See Sweep Line

Deep Dive

One search gives both neighbours

Example: starts = [10, 20] and book(15, 25). The search returns i = 1. The floor is starts[0] = 10, and the ceiling is starts[1] = 20.

Why only the floor and the ceiling can overlap

The calendar holds no overlaps. So when the events are sorted by start, each event ends before the next one starts: ends[j] <= starts[j + 1]. The events are sorted by end too.

Take an event before the floor. It ends no later than the floor starts, and the floor starts at or before startTime. So it ends before the new event starts, and it cannot overlap.

Half-open ends: both comparisons are strict

An event [10, 20) includes 10 and excludes 20. The event [20, 30) starts at 20. The two share no moment, so both can be booked.

The same holds for the ceiling. book(5, 10) when starts = [10, 20]: the check self.starts[i] < endTime is 10 < 10, which is false, so the booking passes.

Equal starts are handled by bisect_right. After book(10, 20), the call book(10, 15) returns i = 1. The floor is [10, 20), and 20 > 10 rejects the booking.

Cost, and a faster structure

bisect_right takes O(log N) time. list.insert shifts every later entry, so it takes O(N) time. One book call costs O(N) time, and the space is O(N).

Insert only after both checks pass. A rejected event that was inserted first would stay in starts and ends and wrongly block later events.

60-Second Pitch

Common Questions

Why is it enough to check only two neighbours?: Stored events do not overlap, so sorted by start they are also sorted by end. Every event before the floor ends before the floor starts. Every event after the ceiling starts after the ceiling ends. If the new event clears the floor and the ceiling, it clears all of them.
Why bisect_right and not bisect_left?: bisect_right puts an event with an equal start before index i, so that event becomes the floor. Its end is greater than startTime, so the floor check rejects the booking. The floor and ceiling have a clear meaning: at most startTime, and greater than startTime.
How would you make the insert fast?: Use a balanced search tree or a skip list, which insert in O(log N) time and offer floor and ceiling lookups. Java's TreeMap has floorKey and ceilingKey. In Python, use a sorted container from a library when it is allowed. Plain lists are O(N) per insert.
What changes if events may overlap, as in My Calendar II (LC 731)?: Two neighbours are no longer enough, because several stored events can overlap the new one. A new event is rejected only when it overlaps a moment that two stored events already cover. Keep the booked events in one list and the intervals that two events cover in a second list, and check the new event against both lists.
Why keep ends as a second list?: The floor check needs the end of the floor event, ends[i - 1]. The two lists share one index, so the end of the event at starts[j] is ends[j]. Both inserts use the same index i.

SWE Reasoning

Spot it

Keys arrive in any order, and between inserts a question asks for the closest stored key at or below a value, or above it.
A new item can conflict only with its nearest neighbours, because the stored items never conflict with each other.
The structure must stay sorted. Sorting again for every query costs O(N log N) time each.
The intervals are half-open, [start, end), so touching ends are allowed.

The invariant, step by step

starts is sorted, and ends[j] is the end of the event that starts at starts[j].
i = bisect.bisect_right(self.starts, startTime) splits starts into values at most startTime and values greater than startTime.
The floor is at i - 1. If self.ends[i - 1] > startTime, the floor event is still running at startTime, and the function returns False.
The ceiling is at i. If self.starts[i] < endTime, the ceiling event starts before the new event ends, and the function returns False.
Stored events do not overlap, so no other stored event can overlap the new one.
Both checks passed, so the function inserts startTime into starts and endTime into ends at the same index i. Both lists stay sorted and aligned.

Traps

>= in the floor check. An event that ends at 20 then blocks one that starts at 20. book(10, 20) followed by book(20, 30) returns False and should return True. The ceiling check < must stay strict for the same reason.
Only one neighbour. For book(10, 20) followed by book(5, 11), there is no floor, and only the ceiling check rejects it. Checking only the floor returns True.
append for ends. ends[j] must pair with starts[j]. append puts the end in the last slot while the start went to index i, so later checks read the wrong end.
Insert before the checks. A rejected event that stays in the lists blocks later events that overlap only the rejected one.
Assuming O(log N) insert. list.insert is O(N). Say this in an interview, and name a balanced tree as the fix.

Practice

Canonical LeetCode:My Calendar I (LC 729)Data Stream as Disjoint Intervals (LC 352)Range Module (LC 715)

Theory Context•Advanced Data Structures

Builds on Lower Bound and Upper Bound, which you haven’t finished yet.

P3MediumMental model~3 min speedrun

Ordered Set (Floor/Ceiling Lookups)

The problem

My Calendar I (LC 729)(opens leetcode.com)

Build a calendar, MyCalendar, that takes events one at a time and keeps only those that fit.

MyCalendar() creates an empty calendar.
boolean book(int startTime, int endTime) adds the event and returns true when it double books with no event already in the calendar. Otherwise it returns false and the calendar stays as it was.

Example 1

Input:["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]]

Output:[null, true, false, true]

[10, 20) is stored. [15, 25) shares moments 15 to 19 with it, so it is rejected. [20, 30) starts exactly where [10, 20) stops, so they share no moment and it is stored.

Ordered Set

sorted keys ➔ bisect position ➔ floor and ceiling neighbours

Spot it when: You insert keys in any order and, between inserts, need the closest stored key at or below a value (the floor) or above it (the ceiling), as in My Calendar I (LC 729).

Ordered Set

Python

1	import bisect
2
3
4	class MyCalendar:
5	"""My Calendar I: keep booked events sorted by start; a new event can only clash with its two neighbours.
6	Time: O(log N) search + O(N) insert per book, N = bookings so far \| Space: O(N)
7	"""
8	def __init__(self) -> None:
9	self.starts: list[int] = [] # Start times of booked events, kept sorted
10	self.ends: list[int] = [] # ends[j] is the end of the event that starts at starts[j]
11
12	def book(self, startTime: int, endTime: int) -> bool:
13	i = bisect.bisect_right(self.starts, startTime) # Events before i start at or before startTime
14
15	# 1. Reject An Overlap With Either Neighbour, Else Insert Between Them:
16	# The floor and ceiling are the only stored events that could possibly overlap the new one,
17	# since every other event sits sorted further away; both half-open checks must stay strict.
18	if i > 0 and self.ends[i - 1] > startTime:
19	return False # Floor neighbour is still running at startTime
20	if i < len(self.starts) and self.starts[i] < endTime:
21	return False # Ceiling neighbour starts before endTime
22	self.starts.insert(i, startTime) # Insert in place: starts stays sorted
23	self.ends.insert(i, endTime)
24	return True

Invariant: starts holds every stored key in sorted order however the inserts arrive, so i = bisect.bisect_right(self.starts, startTime) puts the floor at i - 1 and the ceiling at i.

See it run

An ordered list of starts: floor and ceiling checks

book -i -last result -

Each column is one slot of the sorted lists. The top row is starts, and the bottom row is ends. An empty cell is a slot not used yet.

floor the stored event at or before the new start
ceiling the stored event after the new start
new the event just inserted

No event is booked yet, so starts and ends are empty. Each book call finds its two neighbours with one bisect_right.

starts

ends

1 / 14

Gotchas1 of 5

The trap
Gotcha 1: Writing >= instead of > in the floor check
Mistake
```
if i > 0 and self.ends[i - 1] >= startTime:
```
Fix
```
if i > 0 and self.ends[i - 1] > startTime:
```
What happens: Events are half-open, so [10, 20) and [20, 30) share no moment. With >=, an event that ends at 20 blocks one that starts at 20. The ceiling check self.starts[i] < endTime must stay strict for the same reason.
Example: book(10, 20), then book(20, 30)
Mistake: returns FalseFix: returns True
Gotcha 2: Checking only the floor neighbour
Mistake
```
self.starts.insert(i, startTime)
```
Fix
```
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
```
What happens: The floor is the stored event that starts at or before startTime. It can't see an event that starts inside the new one. After book(10, 20), the new event [5, 11) has no floor. Its ceiling [10, 20) starts before 11, so only the ceiling check rejects it. Checking only the ceiling fails the other way. It misses an event that is still running at startTime.
Example: book(10, 20), then book(5, 11)
Mistake: returns TrueFix: returns False
Gotcha 3: Appending to self.ends instead of inserting at i
Mistake
```
self.ends.append(endTime)
```
Fix
```
self.ends.insert(i, endTime)
```
What happens: self.ends[j] must be the end of the event that starts at self.starts[j]. append puts the end in the last slot, while the start went to slot i. The two lists then pair the wrong starts and ends, and later checks read the wrong end.
Example: book(10, 20), book(0, 5), then book(5, 10)
Mistake: returns FalseFix: returns True

Gotcha 4: Inserting the event before both checks pass

Mistake

self.starts.insert(i, startTime)
self.ends.insert(i, endTime)
if i > 0 and self.ends[i - 1] > startTime:
    return False

Fix

if i > 0 and self.ends[i - 1] > startTime:
    return False
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
self.ends.insert(i, endTime)

Example: book(10, 20), book(15, 25), then book(20, 30)

Mistake: returns FalseFix: returns True

Gotcha 5: Expecting list.insert to take O(log N) time
What happens: bisect_right finds i in O(log N) time, but list.insert shifts every later entry. So one book costs O(N) time. My Calendar I (LC 729) allows at most 1000 calls, so the list is fast enough there. For many more bookings, use a balanced tree with the same floor and ceiling logic. Examples are Java's TreeMap, C++'s std::map and Python's sortedcontainers.SortedList.

Not this one if…

The keys arrive already sorted, as the timestamps in Time Based Key-Value Store (LC 981) do: appending keeps the list in order, so a binary search for the last stored key at or below the query is enough and nothing is ever inserted in the middle. See Upper Bound
The question is how many intervals overlap at the busiest moment, as in Meeting Rooms II (LC 253): every event matters at once, not which single stored key sits closest to one new point. See Sweep Line

Deep Dive

One search gives both neighbours

Example: starts = [10, 20] and book(15, 25). The search returns i = 1. The floor is starts[0] = 10, and the ceiling is starts[1] = 20.

Why only the floor and the ceiling can overlap

The calendar holds no overlaps. So when the events are sorted by start, each event ends before the next one starts: ends[j] <= starts[j + 1]. The events are sorted by end too.

Take an event before the floor. It ends no later than the floor starts, and the floor starts at or before startTime. So it ends before the new event starts, and it cannot overlap.

Half-open ends: both comparisons are strict

An event [10, 20) includes 10 and excludes 20. The event [20, 30) starts at 20. The two share no moment, so both can be booked.

The same holds for the ceiling. book(5, 10) when starts = [10, 20]: the check self.starts[i] < endTime is 10 < 10, which is false, so the booking passes.

Equal starts are handled by bisect_right. After book(10, 20), the call book(10, 15) returns i = 1. The floor is [10, 20), and 20 > 10 rejects the booking.

Cost, and a faster structure

bisect_right takes O(log N) time. list.insert shifts every later entry, so it takes O(N) time. One book call costs O(N) time, and the space is O(N).

Insert only after both checks pass. A rejected event that was inserted first would stay in starts and ends and wrongly block later events.

60-Second Pitch

Common Questions

Why is it enough to check only two neighbours?: Stored events do not overlap, so sorted by start they are also sorted by end. Every event before the floor ends before the floor starts. Every event after the ceiling starts after the ceiling ends. If the new event clears the floor and the ceiling, it clears all of them.
Why bisect_right and not bisect_left?: bisect_right puts an event with an equal start before index i, so that event becomes the floor. Its end is greater than startTime, so the floor check rejects the booking. The floor and ceiling have a clear meaning: at most startTime, and greater than startTime.
How would you make the insert fast?: Use a balanced search tree or a skip list, which insert in O(log N) time and offer floor and ceiling lookups. Java's TreeMap has floorKey and ceilingKey. In Python, use a sorted container from a library when it is allowed. Plain lists are O(N) per insert.
What changes if events may overlap, as in My Calendar II (LC 731)?: Two neighbours are no longer enough, because several stored events can overlap the new one. A new event is rejected only when it overlaps a moment that two stored events already cover. Keep the booked events in one list and the intervals that two events cover in a second list, and check the new event against both lists.
Why keep ends as a second list?: The floor check needs the end of the floor event, ends[i - 1]. The two lists share one index, so the end of the event at starts[j] is ends[j]. Both inserts use the same index i.

SWE Reasoning

Spot it

Keys arrive in any order, and between inserts a question asks for the closest stored key at or below a value, or above it.
A new item can conflict only with its nearest neighbours, because the stored items never conflict with each other.
The structure must stay sorted. Sorting again for every query costs O(N log N) time each.
The intervals are half-open, [start, end), so touching ends are allowed.

The invariant, step by step

starts is sorted, and ends[j] is the end of the event that starts at starts[j].
i = bisect.bisect_right(self.starts, startTime) splits starts into values at most startTime and values greater than startTime.
The floor is at i - 1. If self.ends[i - 1] > startTime, the floor event is still running at startTime, and the function returns False.
The ceiling is at i. If self.starts[i] < endTime, the ceiling event starts before the new event ends, and the function returns False.
Stored events do not overlap, so no other stored event can overlap the new one.
Both checks passed, so the function inserts startTime into starts and endTime into ends at the same index i. Both lists stay sorted and aligned.

Traps

>= in the floor check. An event that ends at 20 then blocks one that starts at 20. book(10, 20) followed by book(20, 30) returns False and should return True. The ceiling check < must stay strict for the same reason.
Only one neighbour. For book(10, 20) followed by book(5, 11), there is no floor, and only the ceiling check rejects it. Checking only the floor returns True.
append for ends. ends[j] must pair with starts[j]. append puts the end in the last slot while the start went to index i, so later checks read the wrong end.
Insert before the checks. A rejected event that stays in the lists blocks later events that overlap only the rejected one.
Assuming O(log N) insert. list.insert is O(N). Say this in an interview, and name a balanced tree as the fix.

Practice

Canonical LeetCode:My Calendar I (LC 729)Data Stream as Disjoint Intervals (LC 352)Range Module (LC 715)

Theory Context•Advanced Data Structures

Builds on Lower Bound and Upper Bound, which you haven’t finished yet.

P3MediumMental model~3 min speedrun

Ordered Set (Floor/Ceiling Lookups)

The problem

My Calendar I (LC 729)(opens leetcode.com)

Build a calendar, MyCalendar, that takes events one at a time and keeps only those that fit.

MyCalendar() creates an empty calendar.
boolean book(int startTime, int endTime) adds the event and returns true when it double books with no event already in the calendar. Otherwise it returns false and the calendar stays as it was.

Example 1

Input:["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]]

Output:[null, true, false, true]

[10, 20) is stored. [15, 25) shares moments 15 to 19 with it, so it is rejected. [20, 30) starts exactly where [10, 20) stops, so they share no moment and it is stored.

Ordered Set

sorted keys ➔ bisect position ➔ floor and ceiling neighbours

Spot it when: You insert keys in any order and, between inserts, need the closest stored key at or below a value (the floor) or above it (the ceiling), as in My Calendar I (LC 729).

Ordered Set

Python

1	import bisect
2
3
4	class MyCalendar:
5	"""My Calendar I: keep booked events sorted by start; a new event can only clash with its two neighbours.
6	Time: O(log N) search + O(N) insert per book, N = bookings so far \| Space: O(N)
7	"""
8	def __init__(self) -> None:
9	self.starts: list[int] = [] # Start times of booked events, kept sorted
10	self.ends: list[int] = [] # ends[j] is the end of the event that starts at starts[j]
11
12	def book(self, startTime: int, endTime: int) -> bool:
13	i = bisect.bisect_right(self.starts, startTime) # Events before i start at or before startTime
14
15	# 1. Reject An Overlap With Either Neighbour, Else Insert Between Them:
16	# The floor and ceiling are the only stored events that could possibly overlap the new one,
17	# since every other event sits sorted further away; both half-open checks must stay strict.
18	if i > 0 and self.ends[i - 1] > startTime:
19	return False # Floor neighbour is still running at startTime
20	if i < len(self.starts) and self.starts[i] < endTime:
21	return False # Ceiling neighbour starts before endTime
22	self.starts.insert(i, startTime) # Insert in place: starts stays sorted
23	self.ends.insert(i, endTime)
24	return True

Invariant: starts holds every stored key in sorted order however the inserts arrive, so i = bisect.bisect_right(self.starts, startTime) puts the floor at i - 1 and the ceiling at i.

See it run

An ordered list of starts: floor and ceiling checks

book -i -last result -

Each column is one slot of the sorted lists. The top row is starts, and the bottom row is ends. An empty cell is a slot not used yet.

floor the stored event at or before the new start
ceiling the stored event after the new start
new the event just inserted

No event is booked yet, so starts and ends are empty. Each book call finds its two neighbours with one bisect_right.

starts

ends

1 / 14

Gotchas1 of 5

The trap
Gotcha 1: Writing >= instead of > in the floor check
Mistake
```
if i > 0 and self.ends[i - 1] >= startTime:
```
Fix
```
if i > 0 and self.ends[i - 1] > startTime:
```
What happens: Events are half-open, so [10, 20) and [20, 30) share no moment. With >=, an event that ends at 20 blocks one that starts at 20. The ceiling check self.starts[i] < endTime must stay strict for the same reason.
Example: book(10, 20), then book(20, 30)
Mistake: returns FalseFix: returns True
Gotcha 2: Checking only the floor neighbour
Mistake
```
self.starts.insert(i, startTime)
```
Fix
```
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
```
What happens: The floor is the stored event that starts at or before startTime. It can't see an event that starts inside the new one. After book(10, 20), the new event [5, 11) has no floor. Its ceiling [10, 20) starts before 11, so only the ceiling check rejects it. Checking only the ceiling fails the other way. It misses an event that is still running at startTime.
Example: book(10, 20), then book(5, 11)
Mistake: returns TrueFix: returns False
Gotcha 3: Appending to self.ends instead of inserting at i
Mistake
```
self.ends.append(endTime)
```
Fix
```
self.ends.insert(i, endTime)
```
What happens: self.ends[j] must be the end of the event that starts at self.starts[j]. append puts the end in the last slot, while the start went to slot i. The two lists then pair the wrong starts and ends, and later checks read the wrong end.
Example: book(10, 20), book(0, 5), then book(5, 10)
Mistake: returns FalseFix: returns True

Gotcha 4: Inserting the event before both checks pass

Mistake

self.starts.insert(i, startTime)
self.ends.insert(i, endTime)
if i > 0 and self.ends[i - 1] > startTime:
    return False

Fix

if i > 0 and self.ends[i - 1] > startTime:
    return False
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
self.ends.insert(i, endTime)

Example: book(10, 20), book(15, 25), then book(20, 30)

Mistake: returns FalseFix: returns True

Gotcha 5: Expecting list.insert to take O(log N) time
What happens: bisect_right finds i in O(log N) time, but list.insert shifts every later entry. So one book costs O(N) time. My Calendar I (LC 729) allows at most 1000 calls, so the list is fast enough there. For many more bookings, use a balanced tree with the same floor and ceiling logic. Examples are Java's TreeMap, C++'s std::map and Python's sortedcontainers.SortedList.

Not this one if…

The keys arrive already sorted, as the timestamps in Time Based Key-Value Store (LC 981) do: appending keeps the list in order, so a binary search for the last stored key at or below the query is enough and nothing is ever inserted in the middle. See Upper Bound
The question is how many intervals overlap at the busiest moment, as in Meeting Rooms II (LC 253): every event matters at once, not which single stored key sits closest to one new point. See Sweep Line

Deep Dive

One search gives both neighbours

Example: starts = [10, 20] and book(15, 25). The search returns i = 1. The floor is starts[0] = 10, and the ceiling is starts[1] = 20.

Why only the floor and the ceiling can overlap

The calendar holds no overlaps. So when the events are sorted by start, each event ends before the next one starts: ends[j] <= starts[j + 1]. The events are sorted by end too.

Take an event before the floor. It ends no later than the floor starts, and the floor starts at or before startTime. So it ends before the new event starts, and it cannot overlap.

Half-open ends: both comparisons are strict

An event [10, 20) includes 10 and excludes 20. The event [20, 30) starts at 20. The two share no moment, so both can be booked.

The same holds for the ceiling. book(5, 10) when starts = [10, 20]: the check self.starts[i] < endTime is 10 < 10, which is false, so the booking passes.

Equal starts are handled by bisect_right. After book(10, 20), the call book(10, 15) returns i = 1. The floor is [10, 20), and 20 > 10 rejects the booking.

Cost, and a faster structure

bisect_right takes O(log N) time. list.insert shifts every later entry, so it takes O(N) time. One book call costs O(N) time, and the space is O(N).

Insert only after both checks pass. A rejected event that was inserted first would stay in starts and ends and wrongly block later events.

60-Second Pitch

Common Questions

Why is it enough to check only two neighbours?: Stored events do not overlap, so sorted by start they are also sorted by end. Every event before the floor ends before the floor starts. Every event after the ceiling starts after the ceiling ends. If the new event clears the floor and the ceiling, it clears all of them.
Why bisect_right and not bisect_left?: bisect_right puts an event with an equal start before index i, so that event becomes the floor. Its end is greater than startTime, so the floor check rejects the booking. The floor and ceiling have a clear meaning: at most startTime, and greater than startTime.
How would you make the insert fast?: Use a balanced search tree or a skip list, which insert in O(log N) time and offer floor and ceiling lookups. Java's TreeMap has floorKey and ceilingKey. In Python, use a sorted container from a library when it is allowed. Plain lists are O(N) per insert.
What changes if events may overlap, as in My Calendar II (LC 731)?: Two neighbours are no longer enough, because several stored events can overlap the new one. A new event is rejected only when it overlaps a moment that two stored events already cover. Keep the booked events in one list and the intervals that two events cover in a second list, and check the new event against both lists.
Why keep ends as a second list?: The floor check needs the end of the floor event, ends[i - 1]. The two lists share one index, so the end of the event at starts[j] is ends[j]. Both inserts use the same index i.

SWE Reasoning

Spot it

Keys arrive in any order, and between inserts a question asks for the closest stored key at or below a value, or above it.
A new item can conflict only with its nearest neighbours, because the stored items never conflict with each other.
The structure must stay sorted. Sorting again for every query costs O(N log N) time each.
The intervals are half-open, [start, end), so touching ends are allowed.

The invariant, step by step

starts is sorted, and ends[j] is the end of the event that starts at starts[j].
i = bisect.bisect_right(self.starts, startTime) splits starts into values at most startTime and values greater than startTime.
The floor is at i - 1. If self.ends[i - 1] > startTime, the floor event is still running at startTime, and the function returns False.
The ceiling is at i. If self.starts[i] < endTime, the ceiling event starts before the new event ends, and the function returns False.
Stored events do not overlap, so no other stored event can overlap the new one.
Both checks passed, so the function inserts startTime into starts and endTime into ends at the same index i. Both lists stay sorted and aligned.

Traps

>= in the floor check. An event that ends at 20 then blocks one that starts at 20. book(10, 20) followed by book(20, 30) returns False and should return True. The ceiling check < must stay strict for the same reason.
Only one neighbour. For book(10, 20) followed by book(5, 11), there is no floor, and only the ceiling check rejects it. Checking only the floor returns True.
append for ends. ends[j] must pair with starts[j]. append puts the end in the last slot while the start went to index i, so later checks read the wrong end.
Insert before the checks. A rejected event that stays in the lists blocks later events that overlap only the rejected one.
Assuming O(log N) insert. list.insert is O(N). Say this in an interview, and name a balanced tree as the fix.

Practice

Canonical LeetCode:My Calendar I (LC 729)Data Stream as Disjoint Intervals (LC 352)Range Module (LC 715)