Find Building Where Alice and Bob Can Meet
Problem
Given heights, a person in building i can move to building j only if i < j and heights[i] < heights[j] (strictly right and strictly taller). For each query [a, b], return the leftmost building both Alice (at a) and Bob (at b) can reach, or -1 if no common meeting building exists.
heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]][2,5,-1,5,2]def leftmostBuildingQueries(heights, queries):
n = len(heights)
ans = [-1] * len(queries)
pend = [[] for _ in range(n)] # pend[b] = (needed_height, query_id)
for i, (a, b) in enumerate(queries):
if a > b:
a, b = b, a # ensure a <= b
if a == b or heights[a] < heights[b]:
ans[i] = b # already reachable, b is leftmost
else:
pend[b].append((heights[a], i)) # defer: search right of b
stack = [] # decreasing heights, index increasing
for r in range(n - 1, -1, -1): # sweep right to left
for need, qid in pend[r]:
lo, hi, pos = 0, len(stack) - 1, -1
while lo <= hi: # binary search the stack
mid = (lo + hi) // 2
if stack[mid][0] > need:
pos = mid # candidate, try a smaller index
lo = mid + 1
else:
hi = mid - 1
if pos != -1:
ans[qid] = stack[pos][1] # leftmost taller building
while stack and stack[-1][0] <= heights[r]:
stack.pop() # keep heights strictly decreasing
stack.append((heights[r], r))
return ansfunction leftmostBuildingQueries(heights, queries) {
const n = heights.length;
const ans = new Array(queries.length).fill(-1);
const pend = Array.from({ length: n }, () => []); // pend[b] = [need, qid]
queries.forEach(([a, b], i) => {
if (a > b) [a, b] = [b, a]; // ensure a <= b
if (a === b || heights[a] < heights[b]) ans[i] = b; // already reachable
else pend[b].push([heights[a], i]); // defer: search right of b
});
const stack = []; // decreasing heights, index increasing
for (let r = n - 1; r >= 0; r--) { // sweep right to left
for (const [need, qid] of pend[r]) {
let lo = 0, hi = stack.length - 1, pos = -1;
while (lo <= hi) { // binary search the stack
const mid = (lo + hi) >> 1;
if (stack[mid][0] > need) { pos = mid; lo = mid + 1; }
else hi = mid - 1;
}
if (pos !== -1) ans[qid] = stack[pos][1]; // leftmost taller building
}
while (stack.length && stack[stack.length - 1][0] <= heights[r]) stack.pop();
stack.push([heights[r], r]); // keep heights strictly decreasing
}
return ans;
}int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
int n = heights.length, m = queries.length;
int[] ans = new int[m];
Arrays.fill(ans, -1);
List<int[]>[] pend = new List[n]; // pend[b] = {need, qid}
for (int i = 0; i < n; i++) pend[i] = new ArrayList<>();
for (int i = 0; i < m; i++) {
int a = queries[i][0], b = queries[i][1];
if (a > b) { int t = a; a = b; b = t; } // ensure a <= b
if (a == b || heights[a] < heights[b]) ans[i] = b;
else pend[b].add(new int[]{heights[a], i});
}
int[][] stack = new int[n][2]; // {height, index}, decreasing
int top = 0;
for (int r = n - 1; r >= 0; r--) { // sweep right to left
for (int[] q : pend[r]) {
int lo = 0, hi = top - 1, pos = -1;
while (lo <= hi) { // binary search the stack
int mid = (lo + hi) >>> 1;
if (stack[mid][0] > q[0]) { pos = mid; lo = mid + 1; }
else hi = mid - 1;
}
if (pos != -1) ans[q[1]] = stack[pos][1];
}
while (top > 0 && stack[top - 1][0] <= heights[r]) top--;
stack[top++] = new int[]{heights[r], r};
}
return ans;
}vector<int> leftmostBuildingQueries(vector<int>& heights,
vector<vector<int>>& queries) {
int n = heights.size(), m = queries.size();
vector<int> ans(m, -1);
vector<vector<pair<int,int>>> pend(n); // pend[b] = {need, qid}
for (int i = 0; i < m; i++) {
int a = queries[i][0], b = queries[i][1];
if (a > b) swap(a, b); // ensure a <= b
if (a == b || heights[a] < heights[b]) ans[i] = b;
else pend[b].push_back({heights[a], i});
}
vector<pair<int,int>> stack; // {height, index}, decreasing
for (int r = n - 1; r >= 0; r--) { // sweep right to left
for (auto& q : pend[r]) {
int lo = 0, hi = (int)stack.size() - 1, pos = -1;
while (lo <= hi) { // binary search the stack
int mid = (lo + hi) / 2;
if (stack[mid].first > q.first) { pos = mid; lo = mid + 1; }
else hi = mid - 1;
}
if (pos != -1) ans[q.second] = stack[pos].second;
}
while (!stack.empty() && stack.back().first <= heights[r]) stack.pop_back();
stack.push_back({heights[r], r});
}
return ans;
}Explanation
You can only walk rightward to a strictly taller building. So a meeting point for buildings a and b (assume a ≤ b after swapping) must be a building t with t ≥ b that is taller than both.
Two easy cases resolve instantly. If a == b they are already together, and if heights[a] < heights[b] then Alice can just climb into Bob's taller building — either way the answer is b, which is also the leftmost possible.
The interesting case is heights[a] ≥ heights[b]. Now b is too short to host the taller person, so we need the smallest index t > b with heights[t] > heights[a]. Because heights[a] ≥ heights[b], beating heights[a] automatically beats heights[b], so one condition suffices.
We answer all such queries offline. Bucket each deferred query under its right endpoint b, then sweep r from right to left maintaining a monotonic stack of (height, index) whose heights are strictly decreasing from bottom to top. At the moment we reach r = b, the stack holds exactly the “visible” buildings to the right of b, ordered so that height decreases as index increases.
That monotonic order lets us binary search the stack for the deepest entry (largest index slot) whose height still exceeds the required value — equivalently the building with the smallest index that is tall enough. That index is the leftmost meeting building.
For heights = [6,4,8,5,2,7] and query [0,3]: heights[0]=6 ≥ heights[3]=5, so we look right of index 3 for the first height above 6. The stack at that point exposes building 5 (height 7), giving the answer 5.