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

The entire core curriculum of 12 patterns and 201 archetypes is 100% free to access with no credit card required. Students receive 40 free compute coins upon registration, +20 daily login coins, and +25 referral coins. A 24-hour unlimited AI coaching pass costs only 5 coins. Alternatively, developers can use Bring-Your-Own-Key (BYOK) for completely free unlimited AI coaching with personal Gemini or OpenAI keys. There are no recurring subscription fees.

What is the refund and cancellation policy?

Hi👋SpeedAlgo has zero recurring subscriptions, zero automatic renewals, and zero hidden billing traps. Because the core platform and learning materials are free, students never face unwanted credit card charges or recurring payment obligations.

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 enforces deliberate practice: proving invariants, articulating Big-O tradeoffs, managing edge cases, and defending algorithmic approaches to a Senior SWE AI Mock Coach in an integrated Monaco code editor.

13. Ordered Set: Time Based Key-Value Store (LC 981) • Invariant Proof & Speed-Run

Theory Context•Advanced Data Structures

MediumLC 981

Time Based Key-Value Store (LeetCode 981)

You will see how a key's history stays sorted for free, so the value that was current at any past moment is one binary search away.

Target Frequency:AmazonGoogleBloomberg

Build a class, TimeMap, that stores values for the same key at different timestamps and looks one up by the timestamp it was current at.

TimeMap() creates an empty store.
void set(key, value, timestamp) records value for key at timestamp. Every timestamp given to set for one key is strictly larger than the timestamp before it.
String get(key, timestamp) returns the value that was set for key at the largest stored timestamp that is still at or before timestamp. When no stored timestamp for key is at or before timestamp, it returns "".

Worked Examples

Example 1

Input:set("temp", "cold", 2); set("temp", "mild", 5); set("temp", "hot", 9); get("temp", 1); get("temp", 5); get("temp", 7)

Output:"", "mild", "mild"

Explanation: get("temp", 1) has no stored timestamp at or before 1, so it returns "". get("temp", 5) matches timestamp 5 exactly. get("temp", 7) has no entry at 7, so the floor is the entry at 5, "mild".

Example 2

Input:set("a", "x", 3); get("a", 3); get("a", 100); get("b", 3)

Output:"x", "x", ""

Explanation: Any timestamp at or after 3 has the same floor, the only entry stored. Key "b" was never set, so its get returns "".

⚖️Formal Constraints & Bounds

1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits
1 <= timestamp <= 10⁷
Every timestamp passed to set for one key is strictly increasing
At most 2 * 10⁵ calls in total to set and get

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Timestamps set for one key only ever grow, so the stored list for a key is sorted the moment it is appended to; the largest stored timestamp at or before a query is then one binary search away with bisect_right, not a scan.

Real-World Scenario & Production Applications

A feature-flag or configuration service that answers "what was this setting's value at time T" from a history of changes: every update is stored with the moment it took effect, and a lookup finds the latest update at or before T without scanning the whole history.

Step-by-Step Execution Trace Table

set("temp", "cold", 2), set("temp", "mild", 5), set("temp", "hot", 9), then three get calls:

Call	`times["temp"]`	`values["temp"]`	`i = bisect_right(...)`	Returns
`set("temp", "cold", 2)`	`[2]`	`["cold"]`		`null`
`set("temp", "mild", 5)`	`[2, 5]`	`["cold", "mild"]`		`null`
`set("temp", "hot", 9)`	`[2, 5, 9]`	`["cold", "mild", "hot"]`		`null`
`get("temp", 1)`			`bisect_right([2,5,9], 1) = 0`	`i == 0`: `""`
`get("temp", 5)`			`bisect_right([2,5,9], 5) = 2`	`values[1] = "mild"`
`get("temp", 7)`			`bisect_right([2,5,9], 7) = 2`	`values[1] = "mild"`

Scroll horizontally to see all columns, or expand to full screen

The list never had to be re-sorted: every set appended a larger timestamp than the one before it. get("temp", 1) is the trap case, i = 0: every stored timestamp is after 1, so there is no floor.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	A stream of timestamps that only ever grows lets a plain list stay sorted with no insert cost: append on `set`, binary search on `get`.
2	Keep this true: `times[key]` holds every timestamp `set` for `key`, in the order they arrived, which is also sorted order.
3	`set`: append to both `times[key]` and `values[key]`. `get`: `i = bisect.bisect_right(times[key], timestamp)`; if `i == 0` there is no floor.
4	The trap: check `i == 0` before reading `values[key][i - 1]`, or a query timestamp before everything ever stored returns the newest value instead of "".

Target: Time Based Key-Value Store (LeetCode 981). LeetCode guarantees every set for a key arrives with a larger timestamp than the last, so appending never breaks the order: no insert, no re-sort.

Boundary Model: Trie Prefix Tree Branching / DSU Near-Flat Forest

Trie: root-to-node path encodes common prefix; DSU: find(u) with path compression flattens tree so root is direct parent.

Loop Invariant Termination

Trie: traverse word char-by-char in O(L); DSU: if find(u) != find(v): union(u, v) in O(alpha(N)).

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Scanning every stored timestamp for a key to find the one at or before a query is O(N) per lookup. But set calls for the same key always arrive with a larger timestamp than the last one -- LeetCode guarantees it -- so simply appending keeps times[key] sorted for free, with no insert cost and no re-sort. Once a list is sorted, finding the floor (the largest stored value at or before a query) is one binary search: bisect_right(stamps, timestamp) returns how many stored stamps are at or before timestamp, so that count minus one is the floor's index. This is the Ordered Set technique: keep keys in order as they arrive, and answer "the closest key at or below x" with bisect instead of a scan.

📖 The Analogy: A Dictionary You Only Ever Add Words To

Picture a dictionary where new entries are only ever added at the end, in alphabetical order, never inserted in the middle. To find the entry that would sort just before or at a new word, you don't read every page: you open near where it would fall and narrow down, exactly like looking up a word by its first letters. Because every earlier set already put the list in order, the search never has to re-sort anything -- it only has to narrow down.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

i = bisect.bisect_right(stamps, timestamp)
if i == 0:
    return ""
return values[i - 1]

bisect_right keeps the invariant that everything before index i is <= timestamp and everything from i on is > timestamp. That invariant holds for every earlier set, because each one only appends a larger stamp at the end -- it never has to be rebuilt. The only value bisect_right can never place at i = 0 is a stamp that has no floor: every stored stamp for that key is already after the query, so get must return "" before reading values[i - 1], or Python's negative indexing quietly returns the newest value instead.

💡 Summary

set appends (O(1) amortized); the list is sorted for free because timestamps only grow. get finds the floor with bisect_right in O(log N), and returns "" when i == 0. O(N) total space.

Reading values[key][-1] by accident: when every stored stamp for key is after timestamp, bisect_right returns i = 0. Skipping the if i == 0: return "" check lets Python's negative indexing turn values[key][i - 1] into values[key][-1], silently returning the newest value.
bisect_left instead of bisect_right: LeetCode allows timestamp_prev == timestamp. bisect_left on an exact match points at that entry itself, so i - 1 returns the value before it, not the exact match; bisect_right points one past it.
Appending to only one of the two lists: values[key][j] must belong to times[key][j]. An early return, or a copy-paste that forgets one .append, desyncs every later lookup for that key.
self.times[key] without .get or .setdefault: a plain [] subscript raises KeyError on a key that was never set; get must handle a missing key, not assume set always ran first.
Re-sorting on every get: timestamps only ever grow per set, so sorted(times[key]) inside get is wasted work every call, turning an O(log N) lookup into O(N log N).

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer hears "strictly increasing timestamps" and reaches straight for a binary search over a scan.

Pattern Recognition Signals

The 10-second spot

"stores values for the same key at different timestamps" with "the largest stored timestamp that is still at or before timestamp": a closest-key-at-or-below lookup while the store keeps growing. "Every timestamp given to set for one key is strictly larger than the timestamp before it" is the signal that no sort or insert is ever needed: Ordered Set, a binary search for the floor.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

times[key] holds every timestamp set for key, always in the order they arrived, which is also sorted order because each one is larger than the last. get computes i = bisect_right(times[key], timestamp); when i > 0, values[key][i - 1] is the floor.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Check i == 0 before reading values[key][i - 1]: when every stored timestamp for key is after the query, Python's negative indexing turns that into values[key][-1], the newest value, instead of "".
Use bisect_right, not bisect_left: an exact match (timestamp_prev == timestamp) is allowed, and bisect_left would point at that entry itself, so i - 1 would skip past it.
Append to both parallel lists on every set: values[key][j] has to stay lined up with times[key][j], or a lookup returns the wrong key's history.
Never re-sort times[key] inside get: the guarantee that timestamps only grow per key is what makes appending enough; sorting on every call turns an O(log N) lookup into O(N log N).

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use an Ordered Set: a floor lookup with bisect. Since LeetCode guarantees every timestamp passed to set for one key is strictly increasing, I can just append to a per-key list on set, and it stays sorted for free, no insert cost, no re-sort. Then get needs the largest stored timestamp at or before the query, the floor, which is one binary search: bisect_right on that key's timestamp list gives me how many stored timestamps are at or before the query, and that count minus one is the floor's index. The trap is when that count is zero: every stored timestamp is after the query, so I have to return empty string before indexing, or Python's negative indexing quietly hands back the newest value instead. Set is O(1) amortized, get is O(log N), and the whole thing is O(N) space.

So: append per key (the list is sorted for free), find the floor with bisect_right, and return "" when i == 0.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(1) amortized per set, O(log N) per get

set does two .append() calls, each amortized O(1) on a Python list, plus one .setdefault() lookup, O(1) average: O(1) amortized per call. get does one .get() lookup, O(1) average, then one bisect.bisect_right call over times[key], which is a binary search, O(log M) where M is the number of timestamps stored for that key; M is at most the total number of set calls, N. So get is O(log N).

SPACE COMPLEXITY

O(N)

times and values together hold one timestamp and one value per set call: O(N) for N calls. No recursion; bisect_right uses O(1) extra space.

Formal Recurrence Relation

get(key, timestamp) = O(log M), M = number of set calls for key so far

Derivation Progression

set

O(1) amortized

.setdefault(key, []).append(timestamp) and .append(value): two amortized-O(1) list appends, no shifting.

get lookup

O(1) average

times.get(key) is one dictionary lookup.

get floor search

O(log M)

bisect.bisect_right(stamps, timestamp) halves the search range each step over the M timestamps stored for key.

Total per get

O(log M) = O(log N)

M never exceeds N, the total number of set calls.

Variable Definitions

$N$

Total number of set calls (at most 2 * 10⁵ combined with get)

$M$

Number of set calls made so far for one particular key (M <= N)

Memory Architecture & Bounds

🟣 Call Stack

O(1): bisect_right is not recursive in CPython's implementation

🔵 Auxiliary Heap

O(1) extra per call: a few integers (i, loop bounds)

🟢 Output Space

O(N) total: times and values store one entry per set call, kept across calls

Boundary Best / Worst Cases

Best Case

$O(1)$ for get: key was never set, so times.get(key) returns None at once

Average Case

$O(\log M)$ per get

Worst Case

$O(\log M)$ for get: every set call so far was for the same key

Pointer Invariant Transition Progression

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "stores values for the same key at different timestamps", "the largest stored timestamp that is still at or before timestamp". Every timestamp given to set for one key strictly larger than the last is the signal that no sort or insert is ever needed: Ordered Set, a floor lookup with bisect_right.

CONSTRAINTS & BOUNDS

At most $2 \times 10^5$ calls combined. A scan per get over one key's history is $O(M)$ ; bisect_right is $O(\log M)$ , where $M$ is that key's call count so far, at most $2 \times 10^5$ .

FAANG PRODUCTION TRAPS & EDGE CASES

i == 0 from bisect_right means no floor exists; reading values[key][i - 1] without that check silently wraps to the newest value in Python. A key never set needs its own check, not a raised KeyError.

Core Algorithmic State Invariants

1. Appending Keeps It Sorted for Free

Every timestamp `set` for one key is strictly larger than the last, so `times[key].append(timestamp)` never breaks sorted order: no insert cost, no re-sort.

2. bisect_right, and Check i == 0

`i = bisect_right(times[key], timestamp)` counts stored stamps `<= timestamp`; `i - 1` is the floor's index. When `i == 0` there is no floor, and `get` must return `""` before indexing, or Python's negative indexing wraps to the newest value.

3. O(1) Amortized Set, O(log N) Get

`set` is two amortized-O(1) list appends. `get` is one dictionary lookup plus one binary search over that key's timestamps: O(log M) for M timestamps stored for that key. O(N) total space.

Theory Context•Advanced Data Structures

MediumLC 981

Time Based Key-Value Store (LeetCode 981)

You will see how a key's history stays sorted for free, so the value that was current at any past moment is one binary search away.

Target Frequency:AmazonGoogleBloomberg

Build a class, TimeMap, that stores values for the same key at different timestamps and looks one up by the timestamp it was current at.

TimeMap() creates an empty store.
void set(key, value, timestamp) records value for key at timestamp. Every timestamp given to set for one key is strictly larger than the timestamp before it.
String get(key, timestamp) returns the value that was set for key at the largest stored timestamp that is still at or before timestamp. When no stored timestamp for key is at or before timestamp, it returns "".

Worked Examples

Example 1

Input:set("temp", "cold", 2); set("temp", "mild", 5); set("temp", "hot", 9); get("temp", 1); get("temp", 5); get("temp", 7)

Output:"", "mild", "mild"

Example 2

Input:set("a", "x", 3); get("a", 3); get("a", 100); get("b", 3)

Output:"x", "x", ""

Explanation: Any timestamp at or after 3 has the same floor, the only entry stored. Key "b" was never set, so its get returns "".

⚖️Formal Constraints & Bounds

1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits
1 <= timestamp <= 10⁷
Every timestamp passed to set for one key is strictly increasing
At most 2 * 10⁵ calls in total to set and get

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

Step-by-Step Execution Trace Table

set("temp", "cold", 2), set("temp", "mild", 5), set("temp", "hot", 9), then three get calls:

Call	`times["temp"]`	`values["temp"]`	`i = bisect_right(...)`	Returns
`set("temp", "cold", 2)`	`[2]`	`["cold"]`		`null`
`set("temp", "mild", 5)`	`[2, 5]`	`["cold", "mild"]`		`null`
`set("temp", "hot", 9)`	`[2, 5, 9]`	`["cold", "mild", "hot"]`		`null`
`get("temp", 1)`			`bisect_right([2,5,9], 1) = 0`	`i == 0`: `""`
`get("temp", 5)`			`bisect_right([2,5,9], 5) = 2`	`values[1] = "mild"`
`get("temp", 7)`			`bisect_right([2,5,9], 7) = 2`	`values[1] = "mild"`

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	A stream of timestamps that only ever grows lets a plain list stay sorted with no insert cost: append on `set`, binary search on `get`.
2	Keep this true: `times[key]` holds every timestamp `set` for `key`, in the order they arrived, which is also sorted order.
3	`set`: append to both `times[key]` and `values[key]`. `get`: `i = bisect.bisect_right(times[key], timestamp)`; if `i == 0` there is no floor.
4	The trap: check `i == 0` before reading `values[key][i - 1]`, or a query timestamp before everything ever stored returns the newest value instead of "".

Target: Time Based Key-Value Store (LeetCode 981). LeetCode guarantees every set for a key arrives with a larger timestamp than the last, so appending never breaks the order: no insert, no re-sort.

Boundary Model: Trie Prefix Tree Branching / DSU Near-Flat Forest

Trie: root-to-node path encodes common prefix; DSU: find(u) with path compression flattens tree so root is direct parent.

Loop Invariant Termination

Trie: traverse word char-by-char in O(L); DSU: if find(u) != find(v): union(u, v) in O(alpha(N)).

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

📖 The Analogy: A Dictionary You Only Ever Add Words To

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

i = bisect.bisect_right(stamps, timestamp)
if i == 0:
    return ""
return values[i - 1]

💡 Summary

Reading values[key][-1] by accident: when every stored stamp for key is after timestamp, bisect_right returns i = 0. Skipping the if i == 0: return "" check lets Python's negative indexing turn values[key][i - 1] into values[key][-1], silently returning the newest value.
bisect_left instead of bisect_right: LeetCode allows timestamp_prev == timestamp. bisect_left on an exact match points at that entry itself, so i - 1 returns the value before it, not the exact match; bisect_right points one past it.
Appending to only one of the two lists: values[key][j] must belong to times[key][j]. An early return, or a copy-paste that forgets one .append, desyncs every later lookup for that key.
self.times[key] without .get or .setdefault: a plain [] subscript raises KeyError on a key that was never set; get must handle a missing key, not assume set always ran first.
Re-sorting on every get: timestamps only ever grow per set, so sorted(times[key]) inside get is wasted work every call, turning an O(log N) lookup into O(N log N).

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer hears "strictly increasing timestamps" and reaches straight for a binary search over a scan.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Check i == 0 before reading values[key][i - 1]: when every stored timestamp for key is after the query, Python's negative indexing turns that into values[key][-1], the newest value, instead of "".
Use bisect_right, not bisect_left: an exact match (timestamp_prev == timestamp) is allowed, and bisect_left would point at that entry itself, so i - 1 would skip past it.
Append to both parallel lists on every set: values[key][j] has to stay lined up with times[key][j], or a lookup returns the wrong key's history.
Never re-sort times[key] inside get: the guarantee that timestamps only grow per key is what makes appending enough; sorting on every call turns an O(log N) lookup into O(N log N).

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use an Ordered Set: a floor lookup with bisect. Since LeetCode guarantees every timestamp passed to set for one key is strictly increasing, I can just append to a per-key list on set, and it stays sorted for free, no insert cost, no re-sort. Then get needs the largest stored timestamp at or before the query, the floor, which is one binary search: bisect_right on that key's timestamp list gives me how many stored timestamps are at or before the query, and that count minus one is the floor's index. The trap is when that count is zero: every stored timestamp is after the query, so I have to return empty string before indexing, or Python's negative indexing quietly hands back the newest value instead. Set is O(1) amortized, get is O(log N), and the whole thing is O(N) space.

So: append per key (the list is sorted for free), find the floor with bisect_right, and return "" when i == 0.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(1) amortized per set, O(log N) per get

SPACE COMPLEXITY

O(N)

times and values together hold one timestamp and one value per set call: O(N) for N calls. No recursion; bisect_right uses O(1) extra space.

Formal Recurrence Relation

get(key, timestamp) = O(log M), M = number of set calls for key so far

Derivation Progression

set

O(1) amortized

.setdefault(key, []).append(timestamp) and .append(value): two amortized-O(1) list appends, no shifting.

get lookup

O(1) average

times.get(key) is one dictionary lookup.

get floor search

O(log M)

bisect.bisect_right(stamps, timestamp) halves the search range each step over the M timestamps stored for key.

Total per get

O(log M) = O(log N)

M never exceeds N, the total number of set calls.

Variable Definitions

$N$

Total number of set calls (at most 2 * 10⁵ combined with get)

$M$

Number of set calls made so far for one particular key (M <= N)

Memory Architecture & Bounds

🟣 Call Stack

O(1): bisect_right is not recursive in CPython's implementation

🔵 Auxiliary Heap

O(1) extra per call: a few integers (i, loop bounds)

🟢 Output Space

O(N) total: times and values store one entry per set call, kept across calls

Boundary Best / Worst Cases

Best Case

$O(1)$ for get: key was never set, so times.get(key) returns None at once

Average Case

$O(\log M)$ per get

Worst Case

$O(\log M)$ for get: every set call so far was for the same key

Pointer Invariant Transition Progression

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

At most $2 \times 10^5$ calls combined. A scan per get over one key's history is $O(M)$ ; bisect_right is $O(\log M)$ , where $M$ is that key's call count so far, at most $2 \times 10^5$ .

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

1. Appending Keeps It Sorted for Free

Every timestamp `set` for one key is strictly larger than the last, so `times[key].append(timestamp)` never breaks sorted order: no insert cost, no re-sort.

2. bisect_right, and Check i == 0

3. O(1) Amortized Set, O(log N) Get

`set` is two amortized-O(1) list appends. `get` is one dictionary lookup plus one binary search over that key's timestamps: O(log M) for M timestamps stored for that key. O(N) total space.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: TIME BASED KEY-VALUE STORE (LEETCODE 981)

T = O(1) amortized per set, O(log N) per getS = O(N)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
Two parallel lists per key, kept sorted for free	`self.times: dict[str, list[int]] = {} self.values: dict[str, list[str]] = {}`	LeetCode guarantees every set for a key arrives with a larger timestamp than the last, so appending never breaks the order: no insert, no re-sort.
Append a new entry	`self.times.setdefault(key, []).append(timestamp) self.values.setdefault(key, []).append(value)`	The two lists stay in lock-step: values[key][j] always belongs to times[key][j].
A key that was never set	`stamps = self.times.get(key) if not stamps: return ""`	`.get(key)` returns None instead of raising, so the missing-key case is one check, not a try/except.
Binary search for the floor	`i = bisect.bisect_right(stamps, timestamp)`	`bisect_right` counts how many stored stamps are at or before `timestamp`; that count is one past the floor's index.
No floor exists (the trap)	`if i == 0: return ""`	When every stored stamp is after `timestamp`, `i` is 0, and `values[key][i - 1]` would silently read the newest value instead of failing.
Read the floor	`return self.values[key][i - 1]`	The floor's timestamp sits at index `i - 1`, and its value sits at the same index in the parallel list.

Call

times["temp"]

values["temp"]

i = bisect_right(...)

Returns

set("temp", "cold", 2)

[2]

["cold"]

null

set("temp", "mild", 5)

[2, 5]

["cold", "mild"]

null

set("temp", "hot", 9)

[2, 5, 9]

["cold", "mild", "hot"]

null

get("temp", 1)

bisect_right([2,5,9], 1) = 0

i == 0: ""

get("temp", 5)

bisect_right([2,5,9], 5) = 2

values[1] = "mild"

get("temp", 7)

bisect_right([2,5,9], 7) = 2

values[1] = "mild"

🧭 Conceptual Foundation & Pattern Intuition

📖 The Analogy: A Dictionary You Only Ever Add Words To

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

i = bisect.bisect_right(stamps, timestamp)
if i == 0:
    return ""
return values[i - 1]

💡 Summary

Call

times["temp"]

values["temp"]

i = bisect_right(...)

Returns

set("temp", "cold", 2)

[2]

["cold"]

null

set("temp", "mild", 5)

[2, 5]

["cold", "mild"]

null

set("temp", "hot", 9)

[2, 5, 9]

["cold", "mild", "hot"]

null

get("temp", 1)

bisect_right([2,5,9], 1) = 0

i == 0: ""

get("temp", 5)

bisect_right([2,5,9], 5) = 2

values[1] = "mild"

get("temp", 7)

bisect_right([2,5,9], 7) = 2

values[1] = "mild"

Canonical Invariant

Concrete Code

Engineering Rationale

Two parallel lists per key, kept sorted for free

self.times: dict[str, list[int]] = {}
self.values: dict[str, list[str]] = {}

LeetCode guarantees every set for a key arrives with a larger timestamp than the last, so appending never breaks the order: no insert, no re-sort.

Append a new entry

self.times.setdefault(key, []).append(timestamp)
self.values.setdefault(key, []).append(value)

The two lists stay in lock-step: values[key][j] always belongs to times[key][j].

A key that was never set

stamps = self.times.get(key)
if not stamps:
    return ""

`.get(key)` returns None instead of raising, so the missing-key case is one check, not a try/except.

Binary search for the floor

i = bisect.bisect_right(stamps, timestamp)

`bisect_right` counts how many stored stamps are at or before `timestamp`; that count is one past the floor's index.

No floor exists (the trap)

if i == 0:
    return ""

When every stored stamp is after `timestamp`, `i` is 0, and `values[key][i - 1]` would silently read the newest value instead of failing.

Read the floor

return self.values[key][i - 1]

The floor's timestamp sits at index `i - 1`, and its value sits at the same index in the parallel list.