2940. Find Building Where Alice and Bob Can Meet - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the i-th 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]. In other words, from a given building, a person can only move rightward to a taller building.

You are also given an array queries where each query is of the form [a_i, b_i]. For the i-th query, Alice starts in building a_i and Bob starts in building b_i. Both can move according to the above rule. The task is to find the leftmost building (smallest index) where Alice and Bob can meet for each query. They can meet in a building if both can reach that building (possibly by making a series of moves). If Alice and Bob cannot move to a common building in a query, the answer for that query should be -1.

Important Details:

If Alice and Bob start in the same building (i.e., a_i == b_i), they are already together, so the answer is that building's index.
"Leftmost building" means among all possible meeting buildings, choose the one with the smallest index (the earliest building).

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:

Query 1: Alice at building 0 (height 6), Bob at building 1 (height 4). They can meet at building 2 (height 8) because 0 < 2 and 6 < 8 (Alice can move 0 → 2) and 1 < 2 and 4 < 8 (Bob can move 1 → 2). Building 2 is the leftmost (smallest index) where they can meet.
Query 2: Alice at 0 (height 6), Bob at 3 (height 5). They meet at building 5 (height 7) since 0 < 5 and 6 < 7 (Alice: 0 → 5) and 3 < 5 and 5 < 7 (Bob: 3 → 5). (Notice Alice could also reach building 2 (height 8), but Bob cannot go backward to 2. Building 5 is the first common reachable.)
Query 3: Alice at 2 (height 8), Bob at 4 (height 2). Alice cannot move anywhere (no taller building to the right of 2), and Bob cannot move left, so no meeting is possible (answer -1).
Query 4: Alice at 3 (height 5), Bob at 4 (height 2). They meet at building 5 (height 7) because 3 < 5 and 5 < 7 (Alice: 3 → 5) and 4 < 5 and 2 < 7 (Bob: 4 → 5). (Building 5 is the first place right of index 4 taller than height 5.)
Query 5: Alice and Bob both at 2. They are already together at building 2.

Constraints:

1 <= heights.length <= 5 * 10^4 (up to 50,000 buildings)
1 <= heights[i] <= 10^9 (building heights)
1 <= queries.length <= 5 * 10^4 (up to 50,000 queries)
0 <= a_i, b_i < heights.length (valid building indices for queries)

The number of buildings and queries can be large (up to 50k each), so an efficient solution is required.

Hints

Understand the movement rule: A person can only move to the right, and only to a taller building. This means someone at a taller building behind cannot catch up to someone ahead at a shorter building (because they can’t move left), and you can’t move to a building of equal or smaller height. Consider how this restricts possible meeting points.
Consider the simplest meeting scenarios: If one person is already at an index that the other can reach directly, that's the meeting point. For example, if one starts ahead (higher index) and has a taller building than the other's height, the other can jump directly there.
Reduce the problem for each query: Without loss of generality, let the person at the smaller index be Alice and the one at the larger index be Bob. Alice can only move rightward (toward Bob or beyond), and Bob is already ahead, so Bob can’t move left. Where can they meet? Think about the conditions on their starting heights.
Key observation: For two starting buildings l (left index) and r (right index), they will either meet at r itself if possible, or at some building to the right of r. They cannot meet at any index less than r (because Bob starts at r and can’t go left). Use this observation to simplify the search space.
Strategy for finding the meeting building: If the left person's building is shorter than the right person's building, then the left person can go directly to the right person's building. If not, you need to find a building to the right that is taller than the taller of the two starting buildings. How can you find the first such taller building efficiently?

Multiple Approaches

We will discuss two approaches: a Brute Force Approach for clarity and an Optimized Approach for efficiency. We’ll explain each with code snippets and analyze their complexity.

1. Brute Force Approach

Idea: For each query, simulate or check possible meeting points. Using our observation, any meeting point must be at index r (the larger index of the two starting positions) or to its right. So for each query, we can do the following:

Let l = min(a, b) and r = max(a, b). (Now l is the left starting index, r is the right starting index.)
If l == r, they start together, so answer is l (or r, same thing).
If heights[l] < heights[r], then Alice (at l) can move directly to building r (since it's to the right and taller), and Bob is already at r. So they meet at r.
Otherwise (if heights[l] >= heights[r]), then Alice cannot move to r (not taller), so the next chance to meet is some building after r. We scan from index = r+1 onward to find the first building taller than heights[l] (because that taller building is the only way Alice can move forward). Let that index be j such that j > r and heights[j] > heights[l]. If found, j is the meeting building (Alice can go l -> j and Bob can go r -> j since it's to the right of r and taller than heights[r] as well). If no such j exists, then there is no possible meeting (return -1).

This brute force essentially checks the condition directly by scanning to the right of r. It’s straightforward but may be slow if done for each query independently.

Pseudocode/Steps:

For each query [a, b]:

l = min(a, b); r = max(a, b)
If l == r: return l.
Else if heights[l] < heights[r]: return r. (Alice can jump to Bob’s building)
Else:
a. Set targetHeight = heights[l].
b. For j from r+1 to n-1 (end of buildings array):
- if heights[j] > targetHeight: return j (found the first taller building).
  c. If loop finishes with no taller found: return -1.

Let's apply this logic to a query manually as a check: Suppose heights = [6,4,8,5,2,7] and query [0,3]. We have l=0 (height=6), r=3 (height=5). 6 >= 5, so not meeting at r. We set targetHeight = 6 and scan from index 4 onward for a height > 6. At index 4, height is 2 (not taller); at index 5, height is 7 (>6) – found it! Return 5. This matches the expected answer.

Brute Force Code (Python):

Python3

. . . .

Brute Force Code (Java):

Java

. . . .

Complexity Analysis (Brute Force): In the worst case, for each query we might scan nearly the entire array to the right of r. In the worst scenario r could be near the beginning for every query and heights[l] is very large (forcing a full scan to the end without finding a taller building). This yields a complexity of about O(n) per query. With Q queries, the worst-case time is O(n * Q). Given n and Q up to 50,000, this could be on the order of 2.5 billion checks in the worst case – far too slow to run within time limits. The space complexity is O(1) extra (not counting output storage), since we only use a few variables for each query.

2. Optimized Approach

To handle up to 50k queries efficiently, we need a faster way to find the first taller building to the right of a given index. Instead of scanning linearly for each query, we can preprocess or use data structures to answer the "next taller building after index r with height > H" query quickly.

Key Observations for Optimization:

Monotonic Stack for Next Greater Element: We can preprocess the next greater element to the right for each building. However, the twist is that the "greater" comparison is against a query-specific height (heights[l]), not necessarily the height of the building itself. A direct next-greater precomputation (which finds the next taller building for each building’s own height) doesn’t fully solve the query because when heights[l] >= heights[r], we are looking for a building taller than heights[l] (which could be much taller than heights[r]). We might need to skip over some that aren’t tall enough. We need a way to query by a height threshold.
Segment Tree or Binary Indexed Tree (Fenwick Tree): We can use a segment tree to store heights and query it by index range and height. Specifically, we can build a segment tree that can answer: “In the range (r+1, end], what is the leftmost index where the height is greater than H?” The segment tree can store the maximum height in each range segment. Then:
1. Check the maximum height in (r+1 ... n-1). If the max height is <= H, then no building beyond r is taller than H – return -1.
2. If the max height > H, we can binary-search on the segment tree: traverse down from the root, always checking the left half first to see if a taller building exists there. This yields the leftmost index with height > H.
Sorting and Binary Search (Offline Queries): Another approach is to handle queries in an offline manner by sorting:
- Pre-sort all building indices by their heights (for example, have a list of (height, index) sorted descending by height).
- Process queries in decreasing order of the threshold height (heights[l]). Maintain a data structure (like a balanced BST or TreeSet) of candidate meeting indices that are tall enough.
- For each query (from highest threshold to lowest): add all building indices whose height is greater than the current threshold to the data structure. These are all buildings tall enough for the current query’s heights[l]. In the data structure (which is sorted by index), quickly find the smallest index that is >= r+1. That will be the answer if it exists (or -1 if none found).
This method uses the fact that as the threshold height decreases, more buildings become "eligible" (so we add them gradually). Each query then just does an order log search in the index set.

We will illustrate the segment tree approach here for clarity, and also provide a Python implementation using the sorting strategy (which is easier in Python using built-in sorted lists or bisect).

Optimized Approach Algorithm (using Segment Tree for clarity):

Pre-build a segment tree over the heights array that can return the maximum height in any given range and also find the index of a height above a given threshold.
For each query [a, b]:
- Compute l = min(a,b), r = max(a,b).
- If l == r: answer = l (same start).
- Else if heights[l] < heights[r]: answer = r (the left person can move to the taller building at r).
- Else (meaning heights[l] >= heights[r]): Use the segment tree to query the range (r+1, n-1) for the first index where height > heights[l].
  - If found, that index is the meeting point.
  - If not found (no taller building in that range), answer = -1.
Return all answers.

Explanation with a Step-by-Step Walkthrough (Optimal Logic):

Let's trace the optimal logic on the example heights = [6,4,8,5,2,7] with a table, using the conditions directly:

Query (a, b)	l = min(a,b)	r = max(a,b)	heights[l] vs heights[r]	Meeting Decision
(0, 1)	0	1	6 (heights[0]) >= 4 (heights[1])	`heights[l] >= heights[r]`, so cannot meet at 1. Find first index >1 with height > 6. Scanning right: index 2 has height 8 (>6) ⇒ answer = 2.
(0, 3)	0	3	6 > 5	Cannot meet at 3. Find first index >3 with height > 6. Check index4: height2 (no); index5: height7 (>6) ⇒ answer = 5.
(2, 4)	2	4	8 >= 2	Cannot meet at 4. Find first index >4 with height > 8. Check index5: height7 (not >8). No index beyond 4 has >8 ⇒ answer = -1 (no meeting possible).
(3, 4)	3	4	5 >= 2	Cannot meet at 4. Find first index >4 with height > 5. Index5: height7 (>5) ⇒ answer = 5.
(2, 2)	2	2	(same index)	They start together ⇒ answer = 2.

In each case, we either directly chose r as the meeting point (when the left building was shorter in height), or we searched to the right of r for the next taller building. This step-by-step logic avoids checking unnecessary indices to the left of r.

Optimized Approach Complexity: Building a segment tree for n heights takes O(n) time, and each query can be answered in O(log n) time (for the height range query and binary search on the tree). Thus, total time is about O((n + Q) log n), which for 50k + 50k is on the order of 100k * log(50k) ≈ 100k * 16 ≈ 1.6 million operations – much faster than brute force. The space complexity is O(n) for the tree. The alternative "sorting + TreeSet" strategy would be O((n + Q) log n) as well (each building added once to the set, each query does a log n search).

Next, we'll provide implementations for the optimal approach in Python and Java, and then discuss common mistakes and edge cases.

Step-by-Step Walkthrough of Optimal Approach

To further clarify, let's do a detailed walkthrough for one of the queries using the segment tree idea:

Consider query (0,3) again with heights = [6,4,8,5,2,7]:

We identify l=0 (height 6) and r=3 (height 5).
Since 6 >= 5, we know building 3 (Bob's position) is not tall enough for Alice to reach. We must look to the right of index 3.
We query the segment tree for the range [4, 5] (since those are indices to the right of 3). The maximum height in this range is 7 (at index 5).
7 is greater than Alice’s height 6, which means there is a candidate meeting building in [4,5] that’s taller than 6.
To find the leftmost such building, we check index 4 first (leftmost in range): height[4] = 2, which is not >6. Then we check index 5: height[5] = 7, which is >6. So index 5 is the answer.
Thus, the tree helps us skip directly to index 5 instead of scanning sequentially.

If no taller building existed in that range, the segment tree would tell us the max height <= 6, and we’d conclude -1 quickly.

The offline sorting approach would handle this query by having added all building indices with height > 6 into a set by the time we process this query. Those heights > 6 in our array are {8,7} corresponding to indices {2,5}. The smallest index > 3 among those is 5, yielding the same answer.

Python Implementation (Optimized Solution with Example)

Python3

. . . .

Java Implementation (Optimized Solution with Segment Tree and TreeSet)

Java

. . . .

Complexity Analysis

Brute Force: As discussed, worst-case time is O(n * Q). With both n and Q up to 50,000, this is potentially ~2.5 billion checks, which is not feasible. Average cases might be faster, but it can easily time out on worst cases. Space usage is minimal (O(1) extra).
Optimized Approaches: Whether using a Segment Tree, Binary Indexed Tree (Fenwick Tree), or the Sorting + TreeSet approach, the complexity will be roughly O((n + Q) log n). Sorting heights and queries takes O(n log n + Q log Q). Processing each query or updating the data structure is O(log n). 50k log(50k) is on the order of a few hundred thousand operations, which is very efficient for modern computers. Space complexity is O(n + Q) for storing auxiliary structures (tree arrays or sets, plus output).

For example, the provided Java solution using TreeSet: sorting takes O(n log n + Q log Q), and then each of up to n insertions and Q TreeSet queries is O(log n), making it O((n+Q) log n + Q log Q). Since Q and n are the same order, this simplifies to O((n+Q) log n). The Python solution uses bisect on a list, which in worst case is O(n) insertion, but since we insert at most n times, the overall complexity is still acceptable (though Python’s constant factors and insertion might be borderline, it's fine for n=50k). A true balanced BST (like TreeSet in Java) avoids the potential O(n) insertion penalty.

Common Mistakes

Not handling the same starting building: Forgetting the case where a == b. In that scenario, the answer should directly be that index (no moves needed). Some might skip this and then their logic might incorrectly return -1 or something else. Always check this first.
Mixing up a and b (order issues): Not ensuring you always treat one as the "left" and the other as "right". If you always assume a is left and b is right, but the input query might be given in any order, you could apply the rule incorrectly. Always take l = min(a,b) and r = max(a,b) (or check both possibilities) so that you know which one is to the right in the array. A common bug is to use the heights comparison without considering indices, or vice versa. Both the index order and height comparison matter.
Allowing movement on equal height or not strictly enforcing taller: The rule is strictly height[i] < height[j]. If you mistakenly allow <=, your logic will fail for cases where heights are equal. Two buildings of equal height cannot move to each other (unless they start together at the same index). Make sure to use strict comparison for height.
Inefficient scanning for each query: Implementing the brute force scanning approach for each query will likely time out. Some might try a BFS/DFS from the starting positions in the graph of allowed moves. That graph could be dense and exploring it fully for each query is too slow. It’s important to use the problem’s constraints (only moving right, needing taller buildings) to cut down the search space.
Off-by-one errors in searching range: When looking for a building to the right of r, be careful to start at r+1 (the building immediately right of Bob’s starting position). Including r in that search by accident could lead to incorrectly suggesting r as the meeting point even when heights don’t allow it. Our logic separately handled the case of meeting at r.
Not returning -1 when appropriate: Ensure that when no meeting is possible (no taller building found to the right), you return -1. A mistake here would be leaving the answer unset or default (like 0) which would be incorrect.

Edge Cases to Consider

Single Building: heights length is 1. There is only building 0. Any query can only be [0,0]. They obviously meet at 0. Our logic should handle this by the l == r check. Also, our data structures should handle ranges of size 0 gracefully (i.e., if r is the last index, we correctly return -1 when looking to the right, unless l == r).
No Possible Move: One or both persons are at a building that has no taller building to its right. For instance, if one starts at the tallest building in the entire array and the other is behind them at any shorter building, then the one behind can never catch up (because the person at the tallest cannot move further, and the one behind cannot reach the tall one if they are shorter or even equal height). Make sure this yields -1. Example: heights = [5,3,1], query [0,2] – Person at 0 (height5) can’t move (no taller to right), person at 2 is ahead but shorter height so can’t move left or right effectively; answer should be -1.
Already Together: As mentioned, if a == b or the scenario where after some moves they effectively are at the same building (which for output means they started same), just return that index.
Many queries with extreme values: If all queries are arranged such that one person is always at index 0 (start) with the maximum height and the other person is at the last index with a very small height, for example, it could stress test performance. Our efficient approach should handle it, but a brute force would not.
Equal Heights Trap: Consider cases like heights = [5,5,5,...] (all equal). No one can move to the right because the height condition fails (no strictly taller building exists for any move). For any query where a != b in such an array, the answer will be -1, because they’re stuck where they are (unless one starts exactly at the same spot). Our logic handles this: if heights are equal, the first check fails (heights[l] < heights[r] is false since they’re equal), and then we look for a taller building to the right. There won’t be any (since all are equal), so we return -1.

Alternative Variations

This problem can be tweaked in various ways:

Allow movement in both directions: If the rule changed so that Alice and Bob could move left or right to taller buildings, the problem would become finding any path in an undirected graph defined by “taller neighbor” relationships. That would be a different problem, potentially solvable with BFS from both sides until a meeting point, but you’d have to be careful to avoid infinite loops and consider the tallest reachable zones.
Allow move to equal-height buildings: If the rule was <= instead of < for heights, then you could move to taller or equal height to the right. In that scenario, a person could move along a plateau of equal heights. The meeting condition would then involve finding a common reachable index considering non-decreasing heights to the right, which changes the solution (we might use a union-find or an extended monotonic stack to group equal heights).
Find rightmost meeting building: Instead of leftmost, find the rightmost (largest index) building they can meet. Given the movement constraints (only rightward movement), the rightmost meeting would often be either the farthest reachable tall building for both or perhaps the end of the array if reachable. This would need a different approach – possibly scanning from the rightmost end backward.
Multiple people meeting: A variation could involve more than two people and finding an index where all of them can convene under similar rules. This complicates the condition intersection but could be handled by generalizing pairwise meets (e.g., maybe find a range that all can reach and then the leftmost in that range).
Graph interpretation: Interpret buildings as nodes in a directed acyclic graph (DAG) where an edge i -> j exists if i<j and heights[i] < heights[j]. Then the problem is to find the lowest-index common reachable node from two start nodes. Variations could ask for the existence of any common node (not necessarily leftmost), or count how many common reachable nodes exist, etc.

Each variation requires adjusting the strategy, but the fundamental concept of "reachable by increasing height" remains central.

Next Greater Element problems (I/II/III) – These involve finding the next greater number either in an array or circular array. They use similar ideas of scanning to the right with a stack.
2736. Maximum Sum Queries – A harder problem that also involves processing queries with conditions on indices and values (mentioned as similar in the editorial). It uses a somewhat similar technique of sorting queries and using a data structure to maintain candidate answers.
Jump Game series (Jump Game I/II/V) – While not directly the same, these involve moving through an array under constraints. For example, Jump Game V allows jumps to the left or right to a higher value with some limits, which has a somewhat similar feel (move only to taller values).
Linked List Intersection – The classic problem of finding the meeting node of two linked list heads is conceptually about two paths meeting at a point. Although the mechanics (linked pointers vs. jumping by height rules) differ, both involve finding a common reachable point.
Graph meet-up problems – More generally, problems that ask if two agents can meet given movement rules. For instance, problems where two people walk along graphs or grids and you check if they land on the same cell at the same time.

2940. Find Building Where Alice and Bob Can Meet - Detailed Explanation

Problem Statement

Hints

Multiple Approaches

1. Brute Force Approach

2. Optimized Approach

Step-by-Step Walkthrough of Optimal Approach

Python Implementation (Optimized Solution with Example)

Java Implementation (Optimized Solution with Segment Tree and TreeSet)

Complexity Analysis

Common Mistakes

Edge Cases to Consider

Alternative Variations

Related Problems