Find Building Where Alice and Bob Can Meet

Find Building Where Alice and Bob Can Meet

What is this problem about?

The Find Building Where Alice and Bob Can Meet interview question presents an array of building heights and several queries. In each query, Alice is at building $a$ and Bob is at building $b$. They want to move to a common building $c$ such that $c \ge \max(a, b)$ and the height of building $c$ is strictly greater than the heights of buildings $a$ and $b$. You need to find the leftmost such building $c$ for each query.

Why is this asked in interviews?

This "Hard" difficulty problem is used by Google and Meta to test advanced data structure knowledge. It combines several concepts: range queries, monotonic properties, and efficient searching. It evaluation your ability to optimize multiple queries over a static array using the Monotonic Stack interview pattern or a Segment Tree.

Algorithmic pattern used

This problem is best solved using Offline Query Processing and a Monotonic Stack (or a Segment Tree/Binary Indexed Tree).

1. Pre-sort queries: Group and sort queries by their rightmost index ($\max(a, b)$).
2. Iterate through buildings: As you move from left to right, maintain a monotonic stack or a segment tree that stores building heights.
3. Process queries: For each query ending at index $i$, find the first building to the right of $i$ that is taller than both $a$ and $b$.
4. By using a Segment Tree that stores the maximum height in a range, you can binary search on the tree to find the leftmost index meeting the height requirement.

Example explanation

Heights: [1, 2, 1, 2, 3]. Query: Alice at 0 (h=1), Bob at 2 (h=1).

1. $\max(0, 2) = 2$.
2. We need a building at index $\ge 2$ with height $> 1$.
3. Building at index 3 has height 2. $2 > 1$.
4. Building 3 is the leftmost valid meeting point. Result: 3.

Common mistakes candidates make

• Online Processing: Trying to solve each query independently in $O(N)$, which leads to $O(Q imes N)$ complexity.
• Ignoring the "leftmost" requirement: Finding any tall building instead of the first one to the right.
• Handling height equality: Not realizing that if Alice and Bob are at the same building or if one is already taller and to the right of the other, they can meet at the rightmost of the two.

Interview preparation tip

When you have many queries about "the first element to the right satisfying condition X," think about Monotonic Stacks or Segment Trees. If you can sort the queries, the "Offline" approach often simplifies the logic significantly.