Delete Columns to Make Sorted

Description

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps, and retrieve the most recent value for a key at or before a given timestamp.

You need to implement the TimeMap class with the following operations:

TimeMap() — Initializes the data structure.
void set(String key, String value, int timestamp) — Stores the string value associated with the string key at the given timestamp.
String get(String key, int timestamp) — Returns the value that was stored for key such that the stored timestamp is the largest timestamp less than or equal to the given timestamp. If there are multiple values satisfying this condition, return the one with the largest stored timestamp. If no such value exists, return an empty string "".

An important guarantee is that all timestamps passed to set are strictly increasing. This means for any particular key, the values are always inserted in chronological order.

Examples

Example 1

Input:

["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]

Output: [null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation:

TimeMap timeMap = new TimeMap(); — Create the data structure.
timeMap.set("foo", "bar", 1); — Store key "foo" with value "bar" at timestamp 1.
timeMap.get("foo", 1); — At timestamp 1, "foo" has value "bar" (exact match), so return "bar".
timeMap.get("foo", 3); — At timestamp 3, there is no exact entry for "foo", but the most recent entry before timestamp 3 is "bar" at timestamp 1. Return "bar".
timeMap.set("foo", "bar2", 4); — Store key "foo" with value "bar2" at timestamp 4.
timeMap.get("foo", 4); — At timestamp 4, "foo" has value "bar2" (exact match), so return "bar2".
timeMap.get("foo", 5); — At timestamp 5, the most recent entry for "foo" at or before 5 is "bar2" at timestamp 4. Return "bar2".

Example 2

Input:

["TimeMap", "set", "set", "get", "get", "get"]
[[], ["key1", "val1", 2], ["key1", "val2", 5], ["key1", 1], ["key1", 3], ["key1", 6]]

Output: [null, null, null, "", "val1", "val2"]

Explanation:

timeMap.set("key1", "val1", 2); — Store "val1" at timestamp 2.
timeMap.set("key1", "val2", 5); — Store "val2" at timestamp 5.
timeMap.get("key1", 1); — Timestamp 1 is before any stored timestamp for "key1". No valid entry exists, return "".
timeMap.get("key1", 3); — The most recent timestamp ≤ 3 is timestamp 2, which stores "val1". Return "val1".
timeMap.get("key1", 6); — The most recent timestamp ≤ 6 is timestamp 5, which stores "val2". Return "val2".

Constraints

1 ≤ key.length, value.length ≤ 100
key and value consist of lowercase English letters and digits.
1 ≤ timestamp ≤ 10^7
All timestamps passed to set are strictly increasing.
At most 2 × 10^5 calls will be made to set and get.

Editorial

Brute Force

Intuition

The simplest way to approach this problem is to store every (timestamp, value) pair for each key and, when we need to retrieve a value, scan through all stored entries for that key from the end to the beginning to find the most recent timestamp that does not exceed our query timestamp.

Think of it like a logbook at a reception desk. Every time someone updates a record, the receptionist writes a new line with the time and value. When asked "what was the value at or before time T?", the receptionist flips backward through the pages until they find the first entry with a time that is ≤ T.

For the set operation, we simply append the (timestamp, value) pair to the list associated with that key in a hash map. Since timestamps are strictly increasing, the list is naturally sorted.

For the get operation, we iterate backward through the list for the given key. The first entry whose timestamp is ≤ the query timestamp is our answer.

Step-by-Step Explanation

Let's trace through the following operations:

set("foo", "bar", 1)
set("foo", "bar2", 4)
get("foo", 3)

Step 1: Call set("foo", "bar", 1). Create an entry for key "foo" in our hash map. Append (1, "bar") to the list.

Store: {"foo": [(1, "bar")]}

Step 2: Call set("foo", "bar2", 4). Append (4, "bar2") to the existing list for "foo".

Store: {"foo": [(1, "bar"), (4, "bar2")]}

Step 3: Call get("foo", 3). Look up key "foo" — it has entries [(1, "bar"), (4, "bar2")].

Step 4: Start scanning from the end of the list. Check the last entry: timestamp 4. Is 4 ≤ 3? No. Skip it.

Step 5: Move to the previous entry: timestamp 1. Is 1 ≤ 3? Yes! Return "bar".

Result: get("foo", 3) returns "bar" — the most recent value stored at or before timestamp 3.

Brute Force — Linear Scan for get("foo", 3) — Watch how we linearly scan backward through the stored entries for key 'foo' to find the most recent timestamp ≤ 3.

Algorithm

Data Structure: Use a hash map where each key maps to a list of (timestamp, value) pairs.
set(key, value, timestamp):
- Append the pair (timestamp, value) to the list for the given key.
- Since timestamps are strictly increasing, the list stays sorted.
get(key, timestamp):
- If the key does not exist in the map, return "".
- Otherwise, iterate backward through the list for that key.
- Return the value of the first entry whose timestamp ≤ the query timestamp.
- If no such entry exists, return "".

Code

#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> store;

public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        if (store.find(key) == store.end()) return "";
        auto& entries = store[key];
        for (int i = entries.size() - 1; i >= 0; i--) {
            if (entries[i].first <= timestamp) {
                return entries[i].second;
            }
        }
        return "";
    }
};

class TimeMap:
    def __init__(self):
        self.store = {}  # key -> list of (timestamp, value)

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        entries = self.store[key]
        for i in range(len(entries) - 1, -1, -1):
            if entries[i][0] <= timestamp:
                return entries[i][1]
        return ""

import java.util.*;

class TimeMap {
    private Map<String, List<int[]>> store;
    private Map<String, List<String>> valueStore;

    public TimeMap() {
        store = new HashMap<>();
        valueStore = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp});
        valueStore.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }

    public String get(String key, int timestamp) {
        if (!store.containsKey(key)) return "";
        List<int[]> timestamps = store.get(key);
        List<String> values = valueStore.get(key);
        for (int i = timestamps.size() - 1; i >= 0; i--) {
            if (timestamps.get(i)[0] <= timestamp) {
                return values.get(i);
            }
        }
        return "";
    }
}

Complexity Analysis

Time Complexity:

set: O(1) — We simply append a pair to the end of a list. Hash map insertion is O(1) amortized.
get: O(n) — In the worst case, we scan through all n entries for a given key. For example, if the query timestamp is smaller than all stored timestamps, we must check every entry before returning "".

Space Complexity: O(m) where m is the total number of set calls. Each call stores one (timestamp, value) pair, and we also maintain the hash map structure.

Why This Approach Is Not Efficient

The brute force get operation takes O(n) time where n is the number of entries for a key. With up to 2 × 10^5 total calls, and each key potentially having thousands of entries, the linear scan becomes a bottleneck.

Consider a scenario: we call set 100,000 times for the same key, then call get 100,000 times with a timestamp smaller than any stored timestamp. Each get scans all 100,000 entries before returning "". That is 100,000 × 100,000 = 10^10 operations — far too slow.

The critical insight is that the list of (timestamp, value) pairs is already sorted by timestamp (since timestamps are strictly increasing). Whenever we need to search for a value in a sorted collection, binary search is the natural choice. Binary search reduces the O(n) scan to O(log n), which is dramatically faster — from 100,000 comparisons down to about 17.

Optimal Approach - Binary Search

Intuition

Since timestamps are inserted in strictly increasing order, the list of (timestamp, value) pairs for each key is always sorted. This is a perfect setup for binary search.

When we call get(key, timestamp), we need to find the largest stored timestamp that is ≤ the query timestamp. This is equivalent to finding the rightmost position where we could insert the query timestamp while keeping the list sorted, and then looking at the element just before that position.

Imagine you have a bookshelf where books are arranged by publication year in ascending order: [1990, 1995, 2000, 2010, 2020]. If someone asks "what was the most recent book published on or before 2005?", you do not flip through every book. Instead, you jump to the middle of the shelf, see that 2000 < 2005 and 2010 > 2005, and immediately know that the 2000 book is the answer. This is exactly how binary search works.

The set operation remains a simple O(1) append. The get operation now uses binary search to find the right entry in O(log n) time.

Step-by-Step Explanation

Let's trace through these operations:

set("user", "active", 1)
set("user", "away", 3)
set("user", "offline", 7)
get("user", 5)

After the three set calls, the store looks like:
{"user": [(1, "active"), (3, "away"), (7, "offline")]}

Now we call get("user", 5) and perform binary search:

Step 1: Look up key "user" in the hash map. Found! The list has 3 entries: timestamps [1, 3, 7]. We need the largest timestamp ≤ 5.

Step 2: Initialize binary search: left = 0, right = 2 (indices of the list). Set result = "" (default if nothing found).

Step 3: Compute mid = (0 + 2) / 2 = 1. Check timestamp at index 1: it is 3. Is 3 ≤ 5? YES. This is a valid candidate. Record result = "away". Since we want the largest valid timestamp, search the right half: set left = mid + 1 = 2.

Step 4: Compute mid = (2 + 2) / 2 = 2. Check timestamp at index 2: it is 7. Is 7 ≤ 5? NO. This timestamp is too large. Search the left half: set right = mid - 1 = 1.

Step 5: Now left = 2 > right = 1, so binary search terminates.

Step 6: Return result = "away". The most recent entry at or before timestamp 5 is (3, "away").

Binary Search — Finding the Most Recent Timestamp ≤ 5 — Watch how binary search narrows the search range to efficiently find the largest stored timestamp that does not exceed the query timestamp of 5.

Algorithm

Data Structure: Use a hash map where each key maps to a list of (timestamp, value) pairs. Since timestamps are strictly increasing, the list is always sorted.
set(key, value, timestamp):
- Append the pair (timestamp, value) to the list for the given key. O(1) operation.
get(key, timestamp):
- If the key does not exist in the map, return "".
- Otherwise, perform binary search on the timestamps list:
  - Initialize left = 0, right = list_length - 1, result = "".
  - While left ≤ right:
    - Compute mid = (left + right) / 2.
    - If the timestamp at mid is ≤ the query timestamp, update result to the value at mid, and set left = mid + 1 (search for an even larger valid timestamp).
    - Otherwise, set right = mid - 1 (current timestamp is too large).
  - Return result.

Code

#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> store;

public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        if (store.find(key) == store.end()) return "";
        auto& entries = store[key];
        int left = 0, right = entries.size() - 1;
        string result = "";
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (entries[mid].first <= timestamp) {
                result = entries[mid].second;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
};

class TimeMap:
    def __init__(self):
        self.store = {}  # key -> list of (timestamp, value)

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        entries = self.store[key]
        left, right = 0, len(entries) - 1
        result = ""
        while left <= right:
            mid = (left + right) // 2
            if entries[mid][0] <= timestamp:
                result = entries[mid][1]
                left = mid + 1
            else:
                right = mid - 1
        return result

import java.util.*;

class TimeMap {
    private Map<String, List<long[]>> timestampStore;
    private Map<String, List<String>> valueStore;

    public TimeMap() {
        timestampStore = new HashMap<>();
        valueStore = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        timestampStore.computeIfAbsent(key, k -> new ArrayList<>()).add(new long[]{timestamp});
        valueStore.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }

    public String get(String key, int timestamp) {
        if (!timestampStore.containsKey(key)) return "";
        List<long[]> timestamps = timestampStore.get(key);
        List<String> values = valueStore.get(key);
        int left = 0, right = timestamps.size() - 1;
        String result = "";
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (timestamps.get(mid)[0] <= timestamp) {
                result = values.get(mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity:

set: O(1) — Appending to the end of a list and hash map insertion are both O(1) amortized.
get: O(log n) — Binary search over the n stored entries for the given key. Each iteration halves the search range, so we need at most ⌈log₂(n)⌉ comparisons.

With up to 2 × 10^5 total calls, and each get taking O(log n) where n ≤ 2 × 10^5, the worst case is about 2 × 10^5 × 17 ≈ 3.4 × 10^6 operations — well within time limits.

Space Complexity: O(m) where m is the total number of set calls. Each set stores one (timestamp, value) pair. The hash map keys themselves take O(k) space where k is the number of unique keys.