leetcode

commit 302f7016844ad2070113f4bf23dcd44fdebff7b1
parent b2245b7df759a72c8aee0739c8167442b1938a22
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 22 Dec 2024 16:36:00 +0100

Daily Problem

Diffstat:
A
Problems/2940.cpp
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 56 insertions(+), 0 deletions(-)
diff --git a/Problems/2940.cpp b/Problems/2940.cpp
@@ -0,0 +1,55 @@
+class Solution {
+    static int search(int height, const vector<pair<int, int>> &st) {
+        int low = 0, high = size(st) - 1;
+        int ans = -1;
+
+        while (low <= high) {
+            const int mid = low + (high - low) / 2;
+
+            if (st[mid].first > height) {
+                ans = max(ans, mid);
+                low = mid + 1;
+            } else {
+                high = mid - 1;
+            }
+        }
+
+        return ans;
+    }
+
+  public:
+    vector<int> leftmostBuildingQueries(const vector<int> &heights, const vector<vector<int>> &queries) {
+        const int n = size(heights), m = size(queries);
+        vector<vector<pair<int, int>>> nqueries(n);
+        vector<int> res(m, -1);
+
+        for (int i = 0; i < m; i++) {
+            int a = queries[i][0];
+            int b = queries[i][1];
+
+            if (a > b) swap(a, b);
+            if (heights[b] > heights[a] || a == b)
+                res[i] = b;
+            else
+                nqueries[b].emplace_back(heights[a], i);
+        }
+
+        vector<pair<int, int>> st;
+        for (int i = n - 1; i >= 0; i--) {
+            for (const auto &[a, b] : nqueries[i]) {
+                const auto pos = search(a, st);
+                if (pos >= 0 && pos < size(st)) {
+                    res[b] = st[pos].second;
+                }
+            }
+
+            while (!st.empty() && st.back().first <= heights[i]) {
+                st.pop_back();
+            }
+
+            st.emplace_back(heights[i], i);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1443,6 +1443,7 @@ reference and a base for solving problems.
 |  2914  |   Medium   | [Minimum Number of Changes to Make Binary String Beautiful](Problems/2914.cpp)                     |
 |  2924  |   Medium   | [Find Champion II](Problems/2924.cpp)                                                              |
 |  2938  |   Medium   | [Separate Black and White Balls](Problems/2938.cpp)                                                |
+|  2940  |    Hard    | [Find Building Where Alice and Bob Can Meet](Problems/2940.cpp)                                    |
 |  2947  |   Medium   | [Count Beautiful Substrings I](Problems/2947.cpp)                                                  |
 |  2952  |   Medium   | [Minimum Number of Coins to be Added](Problems/2952.cpp)                                           |
 |  2957  |   Medium   | [Remove Adjacent Almost-Equal Characters](Problems/2957.cpp)                                       |