Abstract / Summary

A data structure stores key-value pairs with timestamps and retrieves values based on the largest timestamp not exceeding a given time.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 50% (1+ million submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The presented TimeMap class implements a simple in-memory key-value store where each key can have multiple values associated with distinct timestamps. The public interface consists of two operations: set to record a value at a given timestamp, and get to retrieve the most recent value whose timestamp does not exceed a query timestamp. Internally the class relies on a hash table that maps each key to an ordered map of timestamps to values, enabling efficient lookup of the nearest earlier entry.

Core Data Structure

unordered_map<string, map<int, string>> data;

The outer unordered_map provides average-case constant-time access to the bucket that holds all timestamped entries for a particular key. The inner map is a balanced binary search tree ordered by integer timestamps, guaranteeing that entries are kept sorted as they are inserted. This ordering is essential for the binary-search-style lookup performed in the get method.

set Operation

void set(string key, string value, int timestamp) {
    data[key][timestamp] = value;
}

When a caller invokes set, the code first obtains (or creates) the inner map associated with the supplied key via the operator[] of unordered_map. The timestamp serves as the key inside the inner map, and the assignment stores the value. Because map maintains order, each insertion automatically positions the new timestamp relative to existing ones, preserving the chronological sequence without additional work.

Edge Cases Handled

If the same key-timestamp pair is supplied multiple times, the inner map overwrites the previous value with the new one, ensuring that the most recent set call determines the stored value for that exact timestamp. The use of operator[] on the outer hash table also gracefully creates a new inner map when the key has never been seen before, eliminating the need for explicit existence checks.

get Operation

string get(string key, int timestamp) {
    auto slot = data.find(key);
    if (slot == data.end())
        return "";

    auto& bucket = slot->second;

    auto pos = bucket.upper_bound(timestamp);
    if (pos == bucket.begin())
        return "";

    pos--;
    return pos->second;
}

The get method begins by searching the outer hash table for the requested key. If the key does not exist, an empty string is returned immediately, handling the case where no data has ever been stored for that identifier.

Assuming the key is present, a reference to its inner map-named bucket-is obtained. The call to bucket.upper_bound(timestamp) yields an iterator to the first entry whose timestamp is strictly greater than the query timestamp. This step effectively locates the boundary beyond which all entries are too recent.

If the iterator returned by upper_bound points to the beginning of the map, it means that every stored timestamp for the key exceeds the query timestamp. In this situation the method returns an empty string, covering the edge case where the query asks for a time earlier than any recorded value.

When a suitable entry exists, the iterator is moved one step backward (pos--) to point at the greatest timestamp that does not exceed the query timestamp. The associated value is then returned. This backward step is safe because the earlier check guarantees that the iterator is not at begin().

Edge Cases Handled

• Query for a non-existent key returns an empty string.
• Query for a timestamp earlier than the earliest stored timestamp also returns an empty string.
• Multiple values stored at the same timestamp are collapsed to the most recent one due to the overwrite behavior of map.
• Queries that exactly match a stored timestamp are resolved correctly because upper_bound skips only timestamps greater than the query, leaving the matching entry as the predecessor after the decrement.

Performance Optimizations

The combination of an unordered_map for key lookup and a map for timestamp ordering yields a two-level indexing scheme. The outer hash table reduces the average cost of locating the correct bucket to constant time, while the inner balanced tree provides logarithmic time for both insertion and predecessor search. By using upper_bound rather than iterating from the beginning, the get method performs a binary-search-style traversal within the ordered timestamps, avoiding linear scans even when a key has many entries.

Storing timestamps as int keys in the inner map leverages the tree’s natural ordering, eliminating the need for custom comparator logic. The code also avoids unnecessary copying of strings during lookup: the reference auto& bucket prevents a copy of the inner map, and the final return statement yields a reference to the stored string value, which the caller receives as a copy only when needed.

The use of operator[] in set both inserts new keys and updates existing ones without extra conditional branches, streamlining the insertion path. The early-return pattern in get-checking for missing keys and for out-of-range timestamps before any tree traversal-prevents needless work for invalid queries.

Overall, the design balances simplicity with efficient access patterns, ensuring that both set and get operations scale well as the number of keys and timestamps grows.

Imagine a giant magic bookshelf that stores pieces of paper with words on them. The shelf is special because every piece of paper has a secret clock number written in the corner to show when it was saved.

When the set command is used, it acts like a librarian putting a book onto the shelf. The librarian looks for a specific name on the shelf, then finds the right spot for the clock number, and tucks your word inside a little folder labeled with that time.

When the get command is used, it acts like someone looking for a specific name at a certain time. First, it searches the shelf to see if that name exists at all. If the name is there, it opens the folder and looks for the closest clock number that is not past the time requested. If the librarian finds a folder with a time that matches or is just a little bit earlier than the clock, that is the word retrieved. If nothing fits before the requested time, the shelf stays quiet and gives back nothing at all.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: logarithmic
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java							Go
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	bujosa							Rust
	charles-wangkai			Java
	everthis				JS
	fartem								Ruby
	fpdjsns	C++
	fsq	C++
	Garvit244		Python
	halfrost										Go
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	martianoff						Scala
	qiyuangong		Python
	suxrobGM					C#
	varunu28			Java
	vthwang			Java
	yuanliu666									Kotlin
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
martianoff	Scala
qiyuangong	Python
suxrobGM	C#
varunu28	Java
vthwang	Java
yuanliu666	Kotlin
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality