Watch 10 video solutions for Find Building Where Alice and Bob Can Meet, a hard level problem involving Array, Binary Search, Stack. This walkthrough by NeetCodeIO has 13,145 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the ith building.
If a person is in building i, they can move to any other building j if and only if i < j and heights[i] < heights[j].
You are also given another array queries where queries[i] = [ai, bi]. On the ith query, Alice is in building ai while Bob is in building bi.
Return an array ans where ans[i] is the index of the leftmost building where Alice and Bob can meet on the ith query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.
Example 1:
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: In the first query, Alice and Bob can move to building 2 since heights[0] < heights[2] and heights[1] < heights[2]. In the second query, Alice and Bob can move to building 5 since heights[0] < heights[5] and heights[3] < heights[5]. In the third query, Alice cannot meet Bob since Alice cannot move to any other building. In the fourth query, Alice and Bob can move to building 5 since heights[3] < heights[5] and heights[4] < heights[5]. In the fifth query, Alice and Bob are already in the same building. For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet. For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.
Example 2:
Input: heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]] Output: [7,6,-1,4,6] Explanation: In the first query, Alice can directly move to Bob's building since heights[0] < heights[7]. In the second query, Alice and Bob can move to building 6 since heights[3] < heights[6] and heights[5] < heights[6]. In the third query, Alice cannot meet Bob since Bob cannot move to any other building. In the fourth query, Alice and Bob can move to building 4 since heights[3] < heights[4] and heights[0] < heights[4]. In the fifth query, Alice can directly move to Bob's building since heights[1] < heights[6]. For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet. For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.
Constraints:
1 <= heights.length <= 5 * 1041 <= heights[i] <= 1091 <= queries.length <= 5 * 104queries[i] = [ai, bi]0 <= ai, bi <= heights.length - 1Problem Overview: You are given building heights and multiple queries. Each query contains two starting buildings for Alice and Bob. They can only move to the right and only to a building with a strictly greater height. The goal is to return the leftmost building index where both can meet, or -1 if no such building exists.
Approach 1: Next Greater Element Precomputation (O((n+q) log n) time, O(n log n) space)
The movement rule is identical to the classic next greater element pattern. From any building i, the next possible move is the first index to the right with a greater height. Compute this using a monotonic stack in O(n). This forms a directed chain of valid jumps.
For each query (a, b), normalize so a ≤ b. If heights[a] < heights[b], they can meet directly at b. Otherwise, Bob cannot move left, so the answer must be some building to the right of b with height greater than heights[a]. Using the precomputed next-greater links, build binary lifting jump pointers so you can quickly skip through the chain until you find the first building taller than heights[a]. Each query becomes a logarithmic search over the jump table.
This approach works well because the next-greater structure compresses all valid moves into a monotonic chain. Instead of scanning linearly, you jump across increasing heights using precomputed powers of two.
Approach 2: Binary Search on Preprocessed Data (O((n+q) log n) time, O(n) space)
Another strategy processes buildings while maintaining a decreasing stack of candidate indices. The stack represents buildings that could serve as the next taller building for future positions. As you scan from right to left, you remove shorter buildings and maintain a monotonic structure similar to the classic stack next-greater algorithm.
For each query where a ≤ b and heights[a] ≥ heights[b], the meeting building must be to the right of b and must exceed heights[a]. The candidate stack to the right of b is strictly increasing in height, so you can apply binary search to locate the first building whose height is greater than heights[a]. Preprocessing ensures the candidate list remains ordered, making each lookup logarithmic.
This method avoids jump pointers and instead relies on the monotonic property of the stack. Binary search quickly identifies the first valid meeting building.
Recommended for interviews: The monotonic stack preprocessing combined with logarithmic queries is typically expected. It demonstrates understanding of next greater element patterns and efficient query handling. Starting with the brute-force idea (scan to the right for every query) shows the intuition, but the optimized approach using stack-based preprocessing and binary search shows strong algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n * q) | O(1) | Useful for understanding the movement rule before optimization |
| Next Greater Element + Binary Lifting | O((n+q) log n) | O(n log n) | Efficient for many queries and direct navigation along next-greater chains |
| Monotonic Stack + Binary Search | O((n+q) log n) | O(n) | Cleaner implementation when maintaining ordered candidate buildings |