MediumNeetCode150Hash TableBinary SearchDesignData Stream
Time-Based Key-Value Store
Store and retrieve values by timestamp.
Examples
Input
TimeMap: set(foo,bar,1), set(foo,bar,2), get(foo,1)=bar, get(foo,3)=bar
Output
null,null,null,bar,bar
get returns closest value with timestamp <= given.
Constraints
- •
1 <= key.length, value.length <= 100 - •
0 <= timestamp <= 10^7 - •
All valid calls
Approaches
Store (timestamp, value) pairs, linear search.
CodeT: O(n) get | S: O(n) storage
Store sorted timestamps, binary search.
CodeT: O(log n) get | S: O(n) storage
Same approach.
CodeT: O(log n) get | S: O(n) store
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| HashMap + List | O(n) get | O(n) storage | Store (timestamp, value) pairs, linear search. |
| HashMap + Binary Search | O(log n) get | O(n) storage | Store sorted timestamps, binary search. |
| HashMap + Binary Search Optimized | O(log n) get | O(n) store | Same approach. |
HashMap + List
T: O(n) getS: O(n) storage
Store (timestamp, value) pairs, linear search.
HashMap + Binary Search
T: O(log n) getS: O(n) storage
Store sorted timestamps, binary search.
HashMap + Binary Search Optimized
T: O(log n) getS: O(n) store
Same approach.
Common Mistakes
Not handling no key found
Wrong binary search target
Not returning closest timestamp