leetcode

commit 3eb64dbfb796dd9eee39bcb70a99cb464e6e2402
parent 650444fc9a75deeb24a95781963dc30aee38b6af
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 23 Sep 2024 20:41:50 +0200

1 Random Problem

Diffstat:
A
Problems/0981.cpp
 | 
28
++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 29 insertions(+), 0 deletions(-)
diff --git a/Problems/0981.cpp b/Problems/0981.cpp
@@ -0,0 +1,28 @@
+class TimeMap {
+    unordered_map<string, vector<pair<int, string>>> um;
+
+  public:
+    void set(const string &key, const string &value, int timestamp) {
+        um[key].emplace_back(timestamp, value);
+    }
+
+    string get(const string &key, int timestamp) {
+        const auto &vec = um[key];
+        int low = 0, high = size(vec) - 1;
+        string res = "";
+
+        while (low <= high) {
+            const auto mid = low + (high - low) / 2;
+
+            if (vec[mid].first == timestamp) return vec[mid].second;
+            if (vec[mid].first >= timestamp)
+                high = mid - 1;
+            else {
+                res = vec[mid].second;
+                low = mid + 1;
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -619,6 +619,7 @@ for solving problems.
 |  0977  |    Easy    | [Squares of a Sorted Array](Problems/0977.cpp)                                                     |
 |  0979  |   Medium   | [Distribute Coins in Binary Tree](Problems/0979.cpp)                                               |
 |  0980  |    Hard    | [Unique Paths III](Problems/0980.cpp)                                                              |
+|  0981  |   Medium   | [Time Based Key-Value Store](Problems/0981.cpp)                                                    |
 |  0983  |   Medium   | [Minimum Cost For Tickets](Problems/0983.cpp)                                                      |
 |  0985  |   Medium   | [Sum of Even Numbers After Queries](Problems/0985.cpp)                                             |
 |  0986  |   Medium   | [Interval List Intersections](Problems/0986.cpp)                                                   |