This problem requires identifying the leftmost building that both Alice and Bob can reach following strict height rules. Each query asks for a meeting point starting from two given buildings. By applying a binary search over the valid answer space and using monotonic stack optimizations, we can efficiently compute the earliest reachable meeting building or determine if no meeting is possible.
Problem Statement
You are given a 0-indexed array heights of positive integers representing the height of each building. Alice and Bob want to meet, but they can only move from building i to building j if i < j and heights[i] < heights[j].
You are also given an array queries where each query contains two indices [ai, bi]. For each query, determine the leftmost building where both Alice starting at ai and Bob starting at bi can meet. If no such building exists, return -1. Meeting at the same starting building is allowed.
Examples
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]
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]
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 * 104
- 1 <= heights[i] <= 109
- 1 <= queries.length <= 5 * 104
- queries[i] = [ai, bi]
- 0 <= ai, bi <= heights.length - 1
Solution Approach
Precompute Next Greater Buildings
Use a monotonic stack to precompute for each building the next building that is taller. This allows quick access to where Alice or Bob can move next, reducing repeated comparisons for each query.
Binary Search Over Meeting Buildings
For each query [ai, bi], apply binary search on the valid index range to find the leftmost building that both can reach. Swap ai and bi if ai > bi to maintain correct traversal order. Use the precomputed next greater arrays to validate each mid-point efficiently.
Aggregate Answers Efficiently
After validating midpoints using the precomputed arrays, store the earliest valid building for each query. If no valid building exists, return -1. This combines monotonic stack preprocessing with binary search to handle large heights and queries efficiently.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(q \cdot \log q + n) |
| Space | O(n + q) |
The time complexity is O(q * log q + n) due to preprocessing with a monotonic stack and binary search per query. Space complexity is O(n + q) for storing next greater pointers and results.
What Interviewers Usually Probe
- They may ask about optimizing repeated query checks using precomputation.
- Expect clarification questions on why binary search works over the answer space, not the array directly.
- They may probe how to handle queries where Alice and Bob start at the same building.
Common Pitfalls or Variants
Common pitfalls
- Failing to swap query indices when ai > bi, leading to invalid search ranges.
- Overlooking that the meeting building must be taller than both starting buildings.
- Using linear search per query instead of binary search, causing timeouts for large inputs.
Follow-up variants
- Allow movements to buildings with equal height instead of strictly taller.
- Return all possible meeting buildings instead of just the leftmost one.
- Consider bidirectional movement where i > j is also allowed if heights[i] < heights[j].
How GhostInterview Helps
- GhostInterview highlights the binary search pattern over the valid meeting space for each query.
- It suggests using monotonic stacks to precompute next greater buildings, saving repetitive comparisons.
- The solver provides a step-by-step strategy for merging precomputation with efficient query handling.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern to solve Find Building Where Alice and Bob Can Meet?
The key pattern is binary search over the valid answer space combined with monotonic stack precomputation for next taller buildings.
Can Alice and Bob meet at their starting buildings?
Yes, if both start at the same building, that counts as a valid meeting building.
Why do we need to swap ai and bi when ai > bi?
Swapping ensures the binary search moves in the correct direction, maintaining the i < j constraint for valid movements.
What if no building exists where both can meet?
Return -1 for that query, indicating no valid meeting building is reachable from both starting points.
How does monotonic stack help in this problem?
It precomputes the next taller building for each index, allowing quick validation during binary search and avoiding repeated linear scans.
Need direct help with Find Building Where Alice and Bob Can Meet instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Find Building Where Alice and Bob Can Meet from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the maximum sum of paired elements from two arrays under query constraints using efficient binary search techniques.
Open problem page#2454 Next Greater Element IVFind the second greater integer for each element in an array using binary search and monotonic stack techniques.
Open problem page#2945 Find Maximum Non-decreasing Array LengthSolve Find Maximum Non-decreasing Array Length with prefix-sum DP transitions that maximize kept segments while preserving non-decreasing merged sums.
Open problem page