#2940

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Building Where Alice and Bob Can Meet

Determine the leftmost building where Alice and Bob can meet using a binary search over valid move sequences.

array binary search stack binary indexed tree segment tree

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].

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.

terminal

Solution

Solution 1: Binary Indexed Tree

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]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

class BinaryIndexedTree:
    __slots__ = ["n", "c"]

    def __init__(self, n: int):
        self.n = n
        self.c = [inf] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] = min(self.c[x], v)
            x += x & -x

    def query(self, x: int) -> int:
        mi = inf
        while x:
            mi = min(mi, self.c[x])
            x -= x & -x
        return -1 if mi == inf else mi


class Solution:
    def leftmostBuildingQueries(
        self, heights: List[int], queries: List[List[int]]
    ) -> List[int]:
        n, m = len(heights), len(queries)
        for i in range(m):
            queries[i] = [min(queries[i]), max(queries[i])]
        j = n - 1
        s = sorted(set(heights))
        ans = [-1] * m
        tree = BinaryIndexedTree(n)
        for i in sorted(range(m), key=lambda i: -queries[i][1]):
            l, r = queries[i]
            while j > r:
                k = n - bisect_left(s, heights[j]) + 1
                tree.update(k, j)
                j -= 1
            if l == r or heights[l] < heights[r]:
                ans[i] = r
            else:
                k = n - bisect_left(s, heights[l])
                ans[i] = tree.query(k)
        return ans

Continue Practicing

#2736 maximum sum queries #2454 next greater element iv #2945 find maximum non decreasing array length