Find Building Where Alice and Bob Can Meet — Solution
Find Building Where Alice and Bob Can Meet solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Find Building Where Alice and Bob Can Meet is a hard coding problem on arrays, binary search and heap, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Binary Search, Heap, Monotonic Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Buildings stand in a row with heights heights[0..n-1]. A person in building i can move to building j only if i < j and heights[i] < heights[j]; staying put is always allowed.
Each query queries[t] = [a, b] places Alice in building a and Bob in building b. Find the leftmost building where both of them can be — each reaching it in at most one move from their start.
Return an array whose t-th entry is that building's index, or -1 if no building works.
Example 1
Input: heights = [3,1,4,1,5], queries = [[0,1],[1,2],[3,3],[2,0],[4,2]]
Output: [2,2,3,2,4]
Explanation: For [0,1] both can move to building 2 (height 4); for [2,0] Alice is already where Bob can climb to.
Example 2
Input: heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
Output: [2,5,-1,5,2]
Explanation: For [2,4] nothing to the right of building 4 is taller than 8.
Constraints
1 <= heights.length <= 5 * 10^41 <= heights[i] <= 10^91 <= queries.length <= 5 * 10^4queries[t] = [a, b]0 <= a, b <= heights.length - 1
Hints for Find Building Where Alice and Bob Can Meet
Hint 1
Order each query so that
a <= b. Ifa == b, or the person on the left is shorter than the building on the right, the answer is simplyb.Hint 2
Otherwise both must move to some
j > btaller thanheights[a](which is at leastheights[b]) — the answer is the leftmost suchj.Hint 3
Answer those queries offline from right to left: keep a monotonic stack of indices to the right of
bwhose heights are prefix maxima, and binary-search it for the nearest one taller thanheights[a].
How to solve Find Building Where Alice and Bob Can Meet
After sorting each pair so a < b, the hard case asks for the leftmost index after b whose height exceeds heights[a]. Sweeping from the right while maintaining a monotonic stack makes those candidates sorted by both index and height, so each query is one binary search.
Approach
- For each query, let
a = min,b = max. Ifa == borheights[a] < heights[b], the answer isb. Otherwise file the query under indexbwith thresholdv = heights[a]. - Walk
ifromn - 1down to 0. First answer the queries filed underi, then pushiafter popping every stack index whose height is<= heights[i]. - The stack (bottom to top) holds indices with strictly decreasing heights and decreasing positions; the leftmost index taller than
vis the topmost entry whose height is> v. Binary-search the boundary; if no entry is taller, the answer is-1.
Why it works
When queries at i are answered, the stack holds exactly the indices j > i that are taller than everything between i + 1 and j - 1 — the running maxima seen from i. The first index after i that exceeds v is necessarily one of these running maxima, and because heights fall towards the top of the stack, the entries taller than v form a contiguous block at the bottom whose last element is the leftmost such index.
Complexity
- Time —
O((n + q) log n) - Space —
O(n + q)
Pitfalls
- Normalise every query to
a <= bfirst — queries may list Bob before Alice. - Equal heights do not allow a move: the target must be strictly taller than both.
- When
heights[a] < heights[b], buildingbitself is the answer; no search is needed.
Reference solution
Python
from typing import List
def leftmostBuildingQueries(heights: List[int], queries: List[List[int]]) -> List[int]:
n = len(heights)
res = [-1] * len(queries)
pending = [[] for _ in range(n)]
for qi, (x, y) in enumerate(queries):
a, b = min(x, y), max(x, y)
if a == b or heights[a] < heights[b]:
res[qi] = b
else:
pending[b].append((heights[a], qi))
st = []
for i in range(n - 1, -1, -1):
for v, qi in pending[i]:
lo, hi = 0, len(st)
while lo < hi:
mid = (lo + hi) // 2
if heights[st[mid]] > v:
lo = mid + 1
else:
hi = mid
res[qi] = st[lo - 1] if lo > 0 else -1
while st and heights[st[-1]] <= heights[i]:
st.pop()
st.append(i)
return resJava
public static int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
int n = heights.length, qn = queries.length;
int[] res = new int[qn];
Arrays.fill(res, -1);
List<List<Integer>> pending = new ArrayList<>();
for (int i = 0; i < n; i++) pending.add(new ArrayList<>());
for (int q = 0; q < qn; q++) {
int a = Math.min(queries[q][0], queries[q][1]);
int b = Math.max(queries[q][0], queries[q][1]);
if (a == b || heights[a] < heights[b]) res[q] = b;
else pending.get(b).add(q);
}
int[] st = new int[n];
int top = 0;
for (int j = n - 1; j >= 0; j--) {
for (int qi : pending.get(j)) {
int v = heights[Math.min(queries[qi][0], queries[qi][1])];
int lo = 0, hi = top;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (heights[st[mid]] > v) lo = mid + 1; else hi = mid;
}
res[qi] = lo > 0 ? st[lo - 1] : -1;
}
while (top > 0 && heights[st[top - 1]] <= heights[j]) top--;
st[top++] = j;
}
return res;
}C++
vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
int n = heights.size(), qn = queries.size();
vector<int> res(qn, -1);
vector<vector<int>> pending(n);
for (int q = 0; q < qn; q++) {
int a = min(queries[q][0], queries[q][1]);
int b = max(queries[q][0], queries[q][1]);
if (a == b || heights[a] < heights[b]) res[q] = b;
else pending[b].push_back(q);
}
vector<int> st;
for (int j = n - 1; j >= 0; j--) {
for (int qi : pending[j]) {
int v = heights[min(queries[qi][0], queries[qi][1])];
int lo = 0, hi = st.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (heights[st[mid]] > v) lo = mid + 1; else hi = mid;
}
res[qi] = lo > 0 ? st[lo - 1] : -1;
}
while (!st.empty() && heights[st.back()] <= heights[j]) st.pop_back();
st.push_back(j);
}
return res;
}JavaScript
var leftmostBuildingQueries = function(heights, queries) {
var n = heights.length;
var res = new Array(queries.length).fill(-1);
var pending = [];
for (var i = 0; i < n; i++) pending.push([]);
for (var q = 0; q < queries.length; q++) {
var a = Math.min(queries[q][0], queries[q][1]);
var b = Math.max(queries[q][0], queries[q][1]);
if (a === b || heights[a] < heights[b]) res[q] = b;
else pending[b].push(q);
}
var st = [];
for (var j = n - 1; j >= 0; j--) {
var list = pending[j];
for (var t = 0; t < list.length; t++) {
var qi = list[t];
var v = heights[Math.min(queries[qi][0], queries[qi][1])];
var lo = 0, hi = st.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (heights[st[mid]] > v) lo = mid + 1; else hi = mid;
}
res[qi] = lo > 0 ? st[lo - 1] : -1;
}
while (st.length > 0 && heights[st[st.length - 1]] <= heights[j]) st.pop();
st.push(j);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search