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.
This approach involves preprocessing the heights array to identify each building's nearest potential building with greater height. For each query, you can then quickly determine the first such building where both Alice and Bob can move. This significantly reduces unnecessary repeated calculations for multiple queries.
The code first computes the next greater elements for each building using a stack-based approach. The idea is to find the minimum index of the next taller building for each query, where both Alice and Bob can meet. If such a building doesn't exist, the result for that query is -1.
Time Complexity: O(n + q), where n is the number of buildings and q is the number of queries.
Space Complexity: O(n) for storing the next greater elements.
Another approach is to store a list of building heights and their indices and utilize binary searching techniques to efficiently find the first building both Alice and Bob can move to. This approach prioritizes efficient query handling by using sorted data structures.
The C solution preprocesses the building indexes based on their heights for efficient query handling. It then uses binary search to find potential meeting points for each query.
C
Time Complexity: O(n log n + q log n)
Space Complexity: O(n)
Let's denote queries[i] = [l_i, r_i], where l_i \le r_i. If l_i = r_i or heights[l_i] < heights[r_i], then the answer is r_i. Otherwise, we need to find the smallest j among all j > r_i and heights[j] > heights[l_i].
We can sort queries in descending order of r_i, and use a pointer j to point to the current index of heights being traversed.
Next, we traverse each query queries[i] = (l, r). For the current query, if j > r, then we loop to insert heights[j] into the binary indexed tree. The binary indexed tree maintains the minimum index of the suffix height (after discretization). Then, we judge whether l = r or heights[l] < heights[r]. If it is, then the answer to the current query is r. Otherwise, we query the minimum index of heights[l] in the binary indexed tree, which is the answer to the current query.
The time complexity is O((n + m) times log n + m times log m), and the space complexity is O(n + m). Where n and m are the lengths of heights and queries respectively.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Precompute the Next Greater Element | Time Complexity: O(n + q), where n is the number of buildings and q is the number of queries. |
| Binary Search on Preprocessed Data | Time Complexity: O(n log n + q log n) |
| Binary Indexed Tree | — |
| 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 |
Find Building Where Alice and Bob Can Meet - Leetcode 2940 - Python • NeetCodeIO • 13,145 views views
Watch 9 more video solutions →Practice Find Building Where Alice and Bob Can Meet with our built-in code editor and test cases.
Practice on FleetCode