Time Based Key-Value Store (LeetCode 981)
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)recordsvalueforkeyattimestamp. The timestamps passed tosetonly ever grow: each one is strictly larger than every earlier one.String get(key, timestamp)returns the value that wassetforkeyat the largest stored timestamp that is still at or beforetimestamp. When no stored timestamp forkeyis at or beforetimestamp, it returns"".
Worked Examples
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]][null, null, "bar", "bar", null, "bar2", "bar2"]set("foo", "bar", 1), get("foo", 1) matches timestamp 1 exactly, and get("foo", 3) finds nothing stored at 2 or 3, so its floor is the entry at 1, "bar". After set("foo", "bar2", 4), both get("foo", 4) and get("foo", 5) have the entry at 4 as their floor: "bar2".⚖️Formal Constraints & Bounds
1 <= key.length, value.length <= 100keyandvalueconsist of lowercase English letters and digits1 <= timestamp <= 107All timestamps passed to
setare strictly increasingAt most
2 * 105calls in total tosetandget
Core Insight
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
LeetCode's Example 1:
| Call | times["foo"] | values["foo"] | i = bisect_right(...) | Returns |
|---|---|---|---|---|
set("foo", "bar", 1) | [1] | ["bar"] | null | |
get("foo", 1) | bisect_right([1], 1) = 1 | values[0] = "bar" | ||
get("foo", 3) | bisect_right([1], 3) = 1 | values[0] = "bar" | ||
set("foo", "bar2", 4) | [1, 4] | ["bar", "bar2"] | null | |
get("foo", 4) | bisect_right([1, 4], 4) = 2 | values[1] = "bar2" | ||
get("foo", 5) | bisect_right([1, 4], 5) = 2 | values[1] = "bar2" |
The list never had to be re-sorted: every set appended a larger timestamp than the one before it. The example never reaches the trap; get("foo", 0) would: bisect_right([1, 4], 0) = 0, there is no floor, and the answer is "".
| 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 "". |
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, 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. Keys that arrive already sorted need no ordered set: this is the Upper Bound (last True) search on an append-only list, answering "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.
🔑 Why It Works
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.
Reading
values[key][-1]by accident: when every stored stamp forkeyis aftertimestamp,bisect_rightreturnsi = 0. Skipping theif i == 0: return ""check lets Python's negative indexing turnvalues[key][i - 1]intovalues[key][-1], silently returning the newest value.bisect_leftinstead ofbisect_right: LeetCode allowstimestamp_prev == timestamp.bisect_lefton an exact match points at that entry itself, soi - 1returns the value before it, not the exact match;bisect_rightpoints one past it.Appending to only one of the two lists:
values[key][j]must belong totimes[key][j]. An early return, or a copy-paste that leaves out one.append, desyncs every later lookup for that key.self.times[key]without.getor.setdefault: a plain[]subscript raisesKeyErroron a key that was neverset;getmust handle a missing key, not assumesetalways ran first.Re-sorting on every
get: timestamps only ever grow perset, sosorted(times[key])insidegetis wasted work every call, turning anO(log N)lookup intoO(N log N).
4-Phase Thought Process Model
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: a binary search for the floor (Upper Bound), not an ordered set.
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
Append to both parallel lists on every
set:values[key][j]has to stay lined up withtimes[key][j], or a lookup returns the wrong key's history.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a floor lookup with bisect, an Upper Bound search. 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, with no insert cost and 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 isO(log N), and the whole thing isO(N)space.
Complexity & Mathematical Proof
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).
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.
get(key, timestamp) = O(log M), M = number of set calls for key so far
Derivation Progression
O(1) amortized
.setdefault(key, []).append(timestamp) and .append(value): two amortized-O(1) list appends, no shifting.
O(1) average
times.get(key) is one dictionary lookup.
O(log M)
bisect.bisect_right(stamps, timestamp) halves the search range each step over the M timestamps stored for key.
O(log M) = O(log N)
M never exceeds N, the total number of set calls.
Variable Definitions
Total number of set calls (at most 2 * 105 combined with get)
Number of set calls made so far for one particular key (M <= N)
Memory Architecture & Bounds
O(1): bisect_right is not recursive in CPython's implementation
O(1) extra per call: a few integers (i, loop bounds)
O(N) total: times and values store one entry per set call, kept across calls
Boundary Best / Worst Cases
for get: key was never set, so times.get(key) returns None at once
per get
for get: every set call so far was for the same key
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
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: a floor lookup with bisect_right (Upper Bound, the last stored stamp at or before the query), not an ordered set.
At most calls combined. A scan per get over one key's history is ; bisect_right is , where is that key's call count so far, at most .
A key never set needs its own check, not a raised KeyError.
Time Based Key-Value Store (LeetCode 981)
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)recordsvalueforkeyattimestamp. The timestamps passed tosetonly ever grow: each one is strictly larger than every earlier one.String get(key, timestamp)returns the value that wassetforkeyat the largest stored timestamp that is still at or beforetimestamp. When no stored timestamp forkeyis at or beforetimestamp, it returns"".
Worked Examples
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]][null, null, "bar", "bar", null, "bar2", "bar2"]set("foo", "bar", 1), get("foo", 1) matches timestamp 1 exactly, and get("foo", 3) finds nothing stored at 2 or 3, so its floor is the entry at 1, "bar". After set("foo", "bar2", 4), both get("foo", 4) and get("foo", 5) have the entry at 4 as their floor: "bar2".⚖️Formal Constraints & Bounds
1 <= key.length, value.length <= 100keyandvalueconsist of lowercase English letters and digits1 <= timestamp <= 107All timestamps passed to
setare strictly increasingAt most
2 * 105calls in total tosetandget
Core Insight
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
LeetCode's Example 1:
| Call | times["foo"] | values["foo"] | i = bisect_right(...) | Returns |
|---|---|---|---|---|
set("foo", "bar", 1) | [1] | ["bar"] | null | |
get("foo", 1) | bisect_right([1], 1) = 1 | values[0] = "bar" | ||
get("foo", 3) | bisect_right([1], 3) = 1 | values[0] = "bar" | ||
set("foo", "bar2", 4) | [1, 4] | ["bar", "bar2"] | null | |
get("foo", 4) | bisect_right([1, 4], 4) = 2 | values[1] = "bar2" | ||
get("foo", 5) | bisect_right([1, 4], 5) = 2 | values[1] = "bar2" |
The list never had to be re-sorted: every set appended a larger timestamp than the one before it. The example never reaches the trap; get("foo", 0) would: bisect_right([1, 4], 0) = 0, there is no floor, and the answer is "".
| 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 "". |
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, 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. Keys that arrive already sorted need no ordered set: this is the Upper Bound (last True) search on an append-only list, answering "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.
🔑 Why It Works
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.
Reading
values[key][-1]by accident: when every stored stamp forkeyis aftertimestamp,bisect_rightreturnsi = 0. Skipping theif i == 0: return ""check lets Python's negative indexing turnvalues[key][i - 1]intovalues[key][-1], silently returning the newest value.bisect_leftinstead ofbisect_right: LeetCode allowstimestamp_prev == timestamp.bisect_lefton an exact match points at that entry itself, soi - 1returns the value before it, not the exact match;bisect_rightpoints one past it.Appending to only one of the two lists:
values[key][j]must belong totimes[key][j]. An early return, or a copy-paste that leaves out one.append, desyncs every later lookup for that key.self.times[key]without.getor.setdefault: a plain[]subscript raisesKeyErroron a key that was neverset;getmust handle a missing key, not assumesetalways ran first.Re-sorting on every
get: timestamps only ever grow perset, sosorted(times[key])insidegetis wasted work every call, turning anO(log N)lookup intoO(N log N).
4-Phase Thought Process Model
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: a binary search for the floor (Upper Bound), not an ordered set.
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
Append to both parallel lists on every
set:values[key][j]has to stay lined up withtimes[key][j], or a lookup returns the wrong key's history.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a floor lookup with bisect, an Upper Bound search. 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, with no insert cost and 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 isO(log N), and the whole thing isO(N)space.
Complexity & Mathematical Proof
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).
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.
get(key, timestamp) = O(log M), M = number of set calls for key so far
Derivation Progression
O(1) amortized
.setdefault(key, []).append(timestamp) and .append(value): two amortized-O(1) list appends, no shifting.
O(1) average
times.get(key) is one dictionary lookup.
O(log M)
bisect.bisect_right(stamps, timestamp) halves the search range each step over the M timestamps stored for key.
O(log M) = O(log N)
M never exceeds N, the total number of set calls.
Variable Definitions
Total number of set calls (at most 2 * 105 combined with get)
Number of set calls made so far for one particular key (M <= N)
Memory Architecture & Bounds
O(1): bisect_right is not recursive in CPython's implementation
O(1) extra per call: a few integers (i, loop bounds)
O(N) total: times and values store one entry per set call, kept across calls
Boundary Best / Worst Cases
for get: key was never set, so times.get(key) returns None at once
per get
for get: every set call so far was for the same key
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
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: a floor lookup with bisect_right (Upper Bound, the last stored stamp at or before the query), not an ordered set.
At most calls combined. A scan per get over one key's history is ; bisect_right is , where is that key's call count so far, at most .
A key never set needs its own check, not a raised KeyError.