66. Time Based Key-Value Store

🔗 LeetCode Problem: 981. Time Based Key-Value Store
📊 Difficulty: Medium
🏷️ Topics: Hash Table, String, Binary Search, Design

Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

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();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2"

Constraints: - 1 <= key.length, value.length <= 100 - key and value consist of lowercase English letters and digits. - 1 <= timestamp <= 10^7 - All the timestamps timestamp of set are strictly increasing. - At most 2 * 10^5 calls will be made to set and get.

🎨 Visual Understanding

The Problem Visualized

Timeline for key "foo":

Time:  1        2        3        4        5        6
       |        |        |        |        |        |
       bar                        bar2

Operations:
  set("foo", "bar", 1)   → Store at timestamp 1
  get("foo", 1)          → Return "bar" (exact match)
  get("foo", 3)          → Return "bar" (closest ≤ 3 is at 1)
  set("foo", "bar2", 4)  → Store at timestamp 4
  get("foo", 4)          → Return "bar2" (exact match)
  get("foo", 5)          → Return "bar2" (closest ≤ 5 is at 4)

Visual representation:

Key "foo":
  timestamp: [1,      4,      7,      10]
  value:     ["bar", "bar2", "bar3", "bar4"]

Query: get("foo", 8)
  Looking for largest timestamp ≤ 8

  Timeline:
  1    4    7    8    10
  bar bar2 bar3  ?   bar4
              ↑
         Found! 7 ≤ 8

  Return "bar3"

Multiple keys:

Key "foo":
  [1: "bar", 4: "bar2", 7: "bar3"]

Key "baz":
  [2: "hello", 5: "world"]

Key "qux":
  [3: "test"]

get("foo", 5) → "bar2" (largest ≤ 5 is 4)
get("baz", 5) → "world" (exact match at 5)
get("qux", 2) → "" (no timestamp ≤ 2)

🚨 CRITICAL INSIGHT - Binary Search on Timestamps!

The Key Pattern!

Key observation:
  Timestamps are STRICTLY INCREASING for each key
  This means they're SORTED!

When we get(key, timestamp):
  We need: largest timestamp_prev where timestamp_prev ≤ timestamp

This is: "Find largest value ≤ target" in sorted array
       = "Find rightmost valid position"
       = BINARY SEARCH!

Data Structure:
  HashMap<String, List<Pair<Integer, String>>>

  key → List of (timestamp, value) pairs
  List is SORTED by timestamp (guaranteed by input)

Algorithm:
  1. Look up key in HashMap
  2. Binary search on timestamps
  3. Find largest timestamp ≤ query_timestamp
  4. Return corresponding value

Why Binary Search Works Here

For each key, we have sorted timestamps:
  key "foo": [1, 4, 7, 10, 15, 20, ...]

Query: get("foo", 12)
  Need: largest timestamp ≤ 12

  [1, 4, 7, 10, 15, 20]
   ✓  ✓  ✓   ✓   ✗   ✗

  Pattern: [valid valid ... valid | invalid invalid ...]
                              ↑
                         Find this!

This is perfect for binary search!
  - Sorted data ✓
  - Find boundary ✓
  - O(log n) time ✓

The "Find Last Valid" Pattern

We're looking for: LAST timestamp where timestamp ≤ target

Binary search variation:
  Compare mid_timestamp with target

  If mid_timestamp <= target:
    This is valid, but there might be a larger valid
    result = mid (track it)
    left = mid + 1 (search for larger)

  If mid_timestamp > target:
    This is too large
    right = mid - 1 (search for smaller)

After loop: result has the answer

🎯 Approach 1: Linear Search (Brute Force)

The Most Natural Thinking 💭

Core Logic:

Store all (timestamp, value) pairs for each key
For get: scan the list linearly to find largest ≤ timestamp

Implementation

class TimeMap {
    private Map<String, List<Pair>> map;

    class Pair {
        int timestamp;
        String value;
        Pair(int t, String v) {
            timestamp = t;
            value = v;
        }
    }

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

    public void set(String key, String value, int timestamp) {
        map.putIfAbsent(key, new ArrayList<>());
        map.get(key).add(new Pair(timestamp, value));
    }

    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }

        List<Pair> list = map.get(key);
        String result = "";

        // Linear search for largest timestamp <= given timestamp
        for (Pair pair : list) {
            if (pair.timestamp <= timestamp) {
                result = pair.value;
            } else {
                break;  // Since sorted, no need to continue
            }
        }

        return result;
    }
}

⏰ Time: set: O(1), get: O(n) where n = number of timestamps for key
💾 Space: O(n) for all key-value pairs

❌ Problem: get() is too slow for large number of timestamps!

🎯 Approach 2: Binary Search (Optimal) ⭐

Better Approach 💡

🧠 The Core Insight

Timestamps are sorted → Use binary search!

For get(key, timestamp):
  1. Get list of (timestamp, value) pairs
  2. Binary search for largest timestamp ≤ query
  3. Return corresponding value

Time: O(log n) for get ✓

The Strategy:

Data Structure:
  HashMap<String, List<Pair<timestamp, value>>>

set(key, value, timestamp):
  Add to end of list (already sorted)

get(key, timestamp):
  Binary search to find rightmost timestamp ≤ query
  Return corresponding value

Implementation

class TimeMap {
    // Map: key -> list of (timestamp, value) pairs
    private Map<String, List<Pair>> map;

    // Helper class to store timestamp-value pair
    class Pair {
        int timestamp;
        String value;

        Pair(int timestamp, String value) {
            this.timestamp = timestamp;
            this.value = value;
        }
    }

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

    public void set(String key, String value, int timestamp) {
        // Create list if doesn't exist
        map.putIfAbsent(key, new ArrayList<>());

        // Add to end (timestamps are strictly increasing)
        map.get(key).add(new Pair(timestamp, value));
    }

    public String get(String key, int timestamp) {
        // Check if key exists
        if (!map.containsKey(key)) {
            return "";
        }

        List<Pair> list = map.get(key);

        // Binary search for largest timestamp <= given timestamp
        return binarySearch(list, timestamp);
    }

    private String binarySearch(List<Pair> list, int timestamp) {
        int left = 0;
        int right = list.size() - 1;
        String result = "";

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midTimestamp = list.get(mid).timestamp;

            if (midTimestamp == timestamp) {
                // Exact match found
                return list.get(mid).value;
            }

            if (midTimestamp < timestamp) {
                // This is valid, but there might be a larger valid timestamp
                result = list.get(mid).value;
                left = mid + 1;  // Search for larger
            } else {
                // midTimestamp > timestamp, too large
                right = mid - 1;  // Search for smaller
            }
        }

        return result;
    }
}

⏰ Time: set: O(1), get: O(log n) where n = timestamps for key
💾 Space: O(total key-value pairs)

🔍 Dry Run

Example: Operations from problem

Initial state: empty

Operation 1: set("foo", "bar", 1)
─────────────────────────────────────────
  map = {
    "foo": [(1, "bar")]
  }

Operation 2: get("foo", 1)
─────────────────────────────────────────
  list = [(1, "bar")]
  Binary search for timestamp ≤ 1:

  left = 0, right = 0
  mid = 0, midTimestamp = 1
  1 == 1, exact match!
  return "bar" ✓

Operation 3: get("foo", 3)
─────────────────────────────────────────
  list = [(1, "bar")]
  Binary search for timestamp ≤ 3:

  left = 0, right = 0
  mid = 0, midTimestamp = 1
  1 < 3, valid!
  result = "bar"
  left = 1

  Loop ends (left > right)
  return "bar" ✓

Operation 4: set("foo", "bar2", 4)
─────────────────────────────────────────
  map = {
    "foo": [(1, "bar"), (4, "bar2")]
  }

Operation 5: get("foo", 4)
─────────────────────────────────────────
  list = [(1, "bar"), (4, "bar2")]
  Binary search for timestamp ≤ 4:

  left = 0, right = 1
  mid = 0, midTimestamp = 1
  1 < 4, valid!
  result = "bar"
  left = 1

  left = 1, right = 1
  mid = 1, midTimestamp = 4
  4 == 4, exact match!
  return "bar2" ✓

Operation 6: get("foo", 5)
─────────────────────────────────────────
  list = [(1, "bar"), (4, "bar2")]
  Binary search for timestamp ≤ 5:

  left = 0, right = 1
  mid = 0, midTimestamp = 1
  1 < 5, valid!
  result = "bar"
  left = 1

  left = 1, right = 1
  mid = 1, midTimestamp = 4
  4 < 5, valid!
  result = "bar2"
  left = 2

  Loop ends (left > right)
  return "bar2" ✓

Example: Query before any timestamp

State: map = {"foo": [(5, "a"), (10, "b")]}

Query: get("foo", 3)

Binary search for timestamp ≤ 3:
  left = 0, right = 1
  mid = 0, midTimestamp = 5
  5 > 3, too large
  right = -1

  Loop ends (left > right)
  result = "" (never updated)
  return "" ✓

🎯 Why This Works - Deep Dive

The Data Structure Choice:
═══════════════════════════════════════════════════════════════

Why HashMap + List?
  HashMap: O(1) lookup by key
  List: Store chronological data

Why not TreeMap for timestamps?
  TreeMap: O(log n) operations
  ArrayList + Binary Search: Also O(log n)
  But ArrayList has better cache locality!

Why Pair class?
  Bundle timestamp with value
  Keep them together during binary search

The Binary Search Pattern:
═══════════════════════════════════════════════════════════════

This is "Find Last Valid" pattern:
  Looking for LARGEST timestamp ≤ target

  Track result: Save each valid timestamp found
  Keep searching right: Might find larger valid

  When midTimestamp <= target:
    result = mid.value (track it!)
    left = mid + 1 (search for larger)

  When midTimestamp > target:
    right = mid - 1 (search for smaller)

Why Track result Separately?
═══════════════════════════════════════════════════════════════

Without tracking:
  Found valid at mid = 2
  Search right for larger
  Find invalid at mid = 4
  Search left
  Loop ends
  Lost the valid result at 2! ✗

With tracking:
  Found valid at mid = 2
  result = value[2] (saved!)
  Search right
  Find invalid
  Loop ends
  Return result (preserved!) ✓

The Sorted Guarantee:
═══════════════════════════════════════════════════════════════

Problem states: "timestamps of set are strictly increasing"

This means:
  set("foo", "a", 1)
  set("foo", "b", 4)  // 4 > 1 ✓
  set("foo", "c", 7)  // 7 > 4 ✓

List is ALWAYS sorted by timestamp!
No need to sort explicitly!

Time Complexity Analysis:
═══════════════════════════════════════════════════════════════

set(key, value, timestamp):
  HashMap lookup: O(1)
  Add to end of list: O(1)
  Total: O(1) ✓

get(key, timestamp):
  HashMap lookup: O(1)
  Binary search on list: O(log n)
  Total: O(log n) ✓

  where n = number of timestamps for this key

Space: O(total entries)
  Each set stores one entry

Alternative Implementation Using Collections

// Alternative: Use built-in binarySearch
public String get(String key, int timestamp) {
    if (!map.containsKey(key)) {
        return "";
    }

    List<Pair> list = map.get(key);

    // Create dummy pair for binary search
    Pair target = new Pair(timestamp, "");

    int index = Collections.binarySearch(list, target, 
        (a, b) -> Integer.compare(a.timestamp, b.timestamp));

    if (index >= 0) {
        // Exact match
        return list.get(index).value;
    } else {
        // index = -(insertion point) - 1
        // insertion point - 1 = largest element < target
        int insertionPoint = -index - 1;
        if (insertionPoint > 0) {
            return list.get(insertionPoint - 1).value;
        }
        return "";
    }
}

// But custom binary search is clearer and more control!

⚠️ Common Mistakes to Avoid

Mistake 1: Not tracking result

// ❌ WRONG - Loses valid result
while (left <= right) {
    if (mid.timestamp <= target) {
        left = mid + 1;  // No tracking!
    }
}

// ✓ CORRECT - Tracks result
String result = "";
while (left <= right) {
    if (mid.timestamp <= target) {
        result = mid.value;  // Track it!
        left = mid + 1;
    }
}

Mistake 2: Wrong comparison

// ❌ WRONG - Checking equality only
if (midTimestamp == timestamp) {
    return value;
}

// ✓ CORRECT - Need ≤ comparison
if (midTimestamp <= timestamp) {
    result = value;
    left = mid + 1;
}

Mistake 3: Not handling empty key

// ❌ WRONG - NullPointerException
List<Pair> list = map.get(key);
// What if key doesn't exist?

// ✓ CORRECT - Check first
if (!map.containsKey(key)) {
    return "";
}

Mistake 4: Using TreeMap unnecessarily

// ❌ INEFFICIENT - TreeMap overhead
Map<String, TreeMap<Integer, String>> map;

// ✓ BETTER - ArrayList + Binary Search
Map<String, List<Pair>> map;

Mistake 5: Sorting on every get

// ❌ WRONG - Unnecessary sorting
public String get(String key, int timestamp) {
    List<Pair> list = map.get(key);
    Collections.sort(list);  // Already sorted!
    // ...
}

// ✓ CORRECT - Trust input guarantee
// Timestamps are strictly increasing!

🎯 Pattern Recognition

Problem Type: Design + Binary Search
Core Pattern: Time-Based Storage with Range Query

When to Apply:
✓ Need to store versioned data
✓ Timestamps are sequential
✓ Need historical lookups
✓ "Get value at or before time T"
✓ Data is inherently sorted by time

Recognition Keywords:
- "Time-based"
- "At timestamp"
- "Previous value"
- "Strictly increasing timestamps"
- Design data structure

Similar Problems:
- LRU Cache (LC 146) - Different access pattern
- Snapshot Array (LC 1146) - Similar time-based storage
- Design Log Storage System (LC 635)

Key Components:
┌────────────────────────────────────────────┐
│ 1. HashMap for key lookup (O(1))          │
│ 2. List for chronological storage         │
│ 3. Binary search for time queries         │
│ 4. "Find last valid" pattern              │
└────────────────────────────────────────────┘

This combines data structure design with binary search!

🧠 Interview Strategy

Step 1: "Time-based storage → HashMap + List"
Step 2: "Timestamps sorted → Binary search"
Step 3: "Find largest ≤ target → Track result pattern"
Step 4: "Separate set (O(1)) and get (O(log n))"

Key Points to Mention:
- HashMap for O(1) key lookup
- ArrayList stores (timestamp, value) pairs
- Timestamps strictly increasing (pre-sorted)
- Binary search for largest timestamp ≤ query
- Track best result found so far
- Early termination on exact match
- Handle missing keys
- set: O(1), get: O(log n)
- Space: O(total entries)

Design Decisions:
"I'll use a HashMap where each key maps to a list of timestamp-value
pairs. Since timestamps are strictly increasing, the list is already
sorted. For get operations, I'll binary search this list to find the
largest timestamp that doesn't exceed the query timestamp. I track
the best valid result found during the search."

Why Not TreeMap?
"TreeMap would give O(log n) operations, same as ArrayList with
binary search. But ArrayList has better cache locality and the
problem guarantees sorted input, so we don't need TreeMap's
automatic sorting."

Edge Cases:
✓ Query before any timestamp (return "")
✓ Exact timestamp match
✓ Query between timestamps
✓ Key doesn't exist
✓ Multiple timestamps for same key

📝 Quick Revision Notes

🎯 Core Concept:

Time-Based Key-Value Store: Use HashMap + ArrayList. Each key → List of (timestamp, value) pairs. Timestamps are sorted (strictly increasing). For get: binary search for largest timestamp ≤ query. Track result during search! set: O(1), get: O(log n)!

⚡ Quick Implementation:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Pair {
  String value;
  int timestamp;

  public Pair(String value, int timestamp) {
    this.value = value;
    this.timestamp = timestamp;
  } 
}

class TimeMap {
    HashMap<String, List<Pair>> map;

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

    public void set(String key, String value, int timestamp) {
      map.putIfAbsent(key, new ArrayList<>()); // initialize list
      map.get(key).add(new Pair(value, timestamp));
    }

    public String get(String key, int timestamp) {
      String res = "";
      if(!map.containsKey(key)) {
        return res;
      }

      // timestamp_prev <= timestamp. 
      // If there are multiple such values, it returns the value associated with the largest timestamp_prev.
      List<Pair> list = map.get(key);
      // timestamp_prev should be [left, right]
      int left = 0;
      int right = list.size() - 1;

      while (left <= right) {
        int mid = left + (right - left) / 2;
        int timestamp_prev = list.get(mid).timestamp; 
        if(timestamp_prev == timestamp) {
          // got the exact match
          return list.get(mid).value;          
        } else if(timestamp_prev < timestamp) {
          // This is valid, but there might be a larger valid timestamp
          res = list.get(mid).value;
          left = mid + 1;  // Search for larger
        } else {
          right = mid - 1;
        }
      }

      return res;
    }
}

class Test {
  public static void main(String[] args) {
    Test t = new Test();
    t.test();
  }

  private void test() {
    TimeMap tm1 = new TimeMap();
    tm1.set("foo", "bar", 1);
    System.out.println(tm1.get("foo", 1)); // bar
    System.out.println(tm1.get("foo", 3)); // bar
    tm1.set("foo", "bar2", 4);
    System.out.println(tm1.get("foo", 4)); // bar2
    System.out.println(tm1.get("foo", 5)); // bar2

    TimeMap tm2 = new TimeMap();
    tm2.set("love", "high", 10);
    tm2.set("love", "low", 20);
    System.out.println(tm2.get("love", 5)); // ""
    System.out.println(tm2.get("love", 10)); // "high"
    System.out.println(tm2.get("love", 15)); // "high"
    System.out.println(tm2.get("love", 20)); // "low"
    System.out.println(tm2.get("love", 25)); // "low"
  }
}

🔑 Key Insights:

Pattern: Design + Binary Search (Find Last Valid)
Data Structure: HashMap>
Sorted: Timestamps strictly increasing (guaranteed)
set: Append to end - O(1)
get: Binary search - O(log n)
Find: Largest timestamp ≤ query
Track: result variable for best valid
Return: "" if no valid timestamp
Space: O(total entries)

🎪 Memory Aid:

"HashMap + List, timestamps sorted! Binary search, track the best!"
Think: "Time-based = Sorted list = Binary search!"

💡 The Key Insight:

For get(key, timestamp):
  Need: largest timestamp_prev where timestamp_prev ≤ timestamp

  Binary search pattern:
    if (midTime <= timestamp):
      result = value (track it!)
      left = mid + 1 (search for larger)
    else:
      right = mid - 1 (too large)

  Return: result after loop

⚠️ Critical Details:

1. Data: HashMap<String, List<Pair<timestamp, value>>>
2. set: Just append (already sorted)
3. get: Binary search for largest ≤ query
4. Track: String result = ""
5. Update: result = value when valid
6. Continue: left = mid + 1 (find larger)
7. Return: result (or "" if none)

🔥 The Binary Search:

Looking for: LARGEST timestamp ≤ target

[1, 4, 7, 10, 15], target = 12
 ✓  ✓  ✓   ✓   ✗

Find the rightmost ✓ (10)

When midTime <= target:
  Valid! But might be larger valid
  result = value (save it)
  left = mid + 1 (keep searching)

When midTime > target:
  Too large!
  right = mid - 1

💡 Why This Design:

HashMap:
  ✓ O(1) key lookup
  ✓ Support multiple keys

ArrayList:
  ✓ Sequential storage
  ✓ Binary search O(log n)
  ✓ Better cache locality than TreeMap

Pair class:
  ✓ Bundle timestamp + value
  ✓ Keep them together

🧪 Edge Cases

Case 1: Key doesn't exist

get("unknown", 5) → ""

Case 2: Query before first timestamp

set("foo", "a", 5)
get("foo", 3) → ""

Case 3: Exact timestamp match

set("foo", "a", 5)
get("foo", 5) → "a"

Case 4: Query between timestamps

set("foo", "a", 1)
set("foo", "b", 5)
get("foo", 3) → "a"

Case 5: Query after last timestamp

set("foo", "a", 1)
set("foo", "b", 5)
get("foo", 10) → "b"

Case 6: Multiple keys

set("foo", "a", 1)
set("bar", "b", 2)
get("foo", 3) → "a"
get("bar", 3) → "b"

All handled correctly! ✓

LRU Cache (LC 146) - Design with HashMap + DLL
Snapshot Array (LC 1146) - Similar versioning
Design Log Storage System (LC 635) - Time-based retrieval

Happy practicing! 🎯

Note: This is a beautiful combination of data structure design and binary search! The key is recognizing that sorted timestamps enable binary search for O(log n) queries!

66. Time Based Key-Value Store

Problem Statement

🎨 Visual Understanding

The Problem Visualized

🚨 CRITICAL INSIGHT - Binary Search on Timestamps!

Why Binary Search Works Here

The "Find Last Valid" Pattern

🎯 Approach 1: Linear Search (Brute Force)

The Most Natural Thinking 💭

Implementation

🎯 Approach 2: Binary Search (Optimal) ⭐

Better Approach 💡

Implementation

🔍 Dry Run

🎯 Why This Works - Deep Dive

Alternative Implementation Using Collections

⚠️ Common Mistakes to Avoid

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

🧪 Edge Cases

Related Patterns