# Find Building Where Alice and Bob Can Meet
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-building-where-alice-and-bob-can-meet)
Canonical: https://scaleengineer.com/dsa/problems/find-building-where-alice-and-bob-can-meet
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Stack, Heap (Priority Queue), Monotonic Stack, Binary Indexed Tree, Segment Tree
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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 * 104`
* `1 <= heights[i] <= 109`
* `1 <= queries.length <= 5 * 104`
* `queries[i] = [ai, bi]`
* `0 <= ai, bi <= heights.length - 1`

# Approaches
## Brute Force Iteration
This approach directly simulates the process for each query. For every query `[a, b]`, we first check for simple cases: if they are at the same building, or if one can move to the other's building. If not, we perform a linear scan through the buildings to the right of both Alice and Bob to find the first suitable meeting place.
**Time:** O(Q * N) - For each of the Q queries, we might perform a linear scan of up to N elements in the worst case. Here, N is the number of buildings and Q is the number of queries. · **Space:** O(Q) or O(1) - The space required is primarily for the output array, which is of size Q. If modifying the input or printing is allowed, it can be considered O(1) auxiliary space.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** The time complexity of O(Q * N) is too high for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
For each query `[a, b]`, we determine the conditions for a meeting. A meeting can happen at a building `k` if `k` is to the right of both `a` and `b`, and `heights[k]` is greater than both `heights[a]` and `heights[b]`. Let's define `v = max(a, b)` and `h_req = max(heights[a], heights[b])`. The problem then becomes finding the smallest index `k > v` such that `heights[k] > h_req`.

There are some special conditions to consider first. If `a` and `b` are the same, they have already met, so the answer is `a`. If `a` and `b` are different, let's say `a < b`. If `heights[a] < heights[b]`, Alice can move to Bob's building `b`. Since any other potential meeting place `k` must satisfy `k > b`, `b` is the leftmost possible option. Thus, the answer is `b`. A similar logic applies if `b < a`.

If these special conditions don't apply, we must search for a building `k`. The brute-force method involves a simple linear scan starting from `v + 1` to the end of the `heights` array, checking the height condition at each step. The first building that satisfies the condition is our answer. If no such building is found after checking all possibilities, it's impossible for them to meet, so we return -1.

```java
class Solution {
    public int[] canMeet(int[] heights, int[][] queries) {
        int n = heights.length;
        int q = queries.length;
        int[] ans = new int[q];

        for (int i = 0; i < q; i++) {
            int u = queries[i][0];
            int v = queries[i][1];

            if (u == v) {
                ans[i] = u;
                continue;
            }

            if (u > v) {
                int temp = u;
                u = v;
                v = temp;
            }
            // Now u < v

            if (heights[u] < heights[v]) {
                ans[i] = v;
                continue;
            }

            // Now u < v and heights[u] >= heights[v]
            // Required height is heights[u]
            int requiredHeight = heights[u];
            int meetingPoint = -1;
            for (int k = v + 1; k < n; k++) {
                if (heights[k] > requiredHeight) {
                    meetingPoint = k;
                    break;
                }
            }
            ans[i] = meetingPoint;
        }
        return ans;
    }
}
```
### Algorithm
- For each query `[a, b]`:
- Handle the base cases:
  - If `a == b`, they are at the same building. The answer is `a`.
  - To simplify, let `u = min(a, b)` and `v = max(a, b)`.
  - If `heights[u] < heights[v]`, the person at `u` can move to building `v`. Since any other meeting place `k` must be `k > v`, `v` is the leftmost possible meeting place. The answer is `v`.
- If none of the above conditions are met, it means `v > u` and `heights[v] <= heights[u]`. They must find a common building `k` to meet.
- The conditions for a meeting at building `k` are:
  - `k > u` and `heights[k] > heights[u]`
  - `k > v` and `heights[k] > heights[v]`
- Combining these, we need to find the smallest `k` such that `k > v` and `heights[k] > max(heights[u], heights[v])`.
- Iterate `k` from `v + 1` to `heights.length - 1`.
- The first `k` that satisfies `heights[k] > max(heights[u], heights[v])` is the answer.
- If the loop completes without finding such a `k`, no such meeting place exists, and the answer is -1.

## Offline Processing with Monotonic Stack
The brute-force approach is slow because it repeatedly scans the `heights` array. We can optimize this by processing queries offline. The key observation is that for a query `[a, b]`, the search for a meeting place `k` always starts from `max(a, b) + 1`. This suggests we can process queries based on their starting search position.

We can group queries by `v = max(a, b)` and then iterate through the `heights` array from right to left. As we iterate from `i = N-1` down to `0`, we maintain a data structure of all potential 'next greater buildings' for indices to the right of `i`. A monotonic stack is perfect for this. The stack will store `(height, index)` pairs, pruned of all non-optimal candidates.
**Time:** O(N + Q log N) - Preprocessing queries takes O(Q). The main loop runs N times. Inside the loop, each of the Q queries is processed once with a binary search on the stack, which takes O(log N). Updating the stack takes amortized O(1) time per element. Total time is dominated by processing queries. · **Space:** O(N + Q) - We need O(Q) space to store the categorized queries and the answer array. The monotonic stack can grow up to size O(N) in the worst case (e.g., a strictly decreasing heights array).
**Pros:** Highly efficient, with a time complexity that passes the given constraints.; Effectively uses a combination of standard algorithmic techniques (offline processing, monotonic stack).
**Cons:** The implementation is more complex than the brute-force approach.; Requires careful handling of data structures (map for queries, list for stack) and binary search logic.
### Explanation
This approach leverages offline processing and a monotonic stack to answer queries efficiently.

First, we categorize the queries. Some can be answered immediately: if `a == b`, the answer is `a`. If `a < b` and `heights[a] < heights[b]`, the answer is `b` (and vice-versa). The remaining queries require a search. For each such query `[a, b]`, we need to find the smallest `k > v = max(a, b)` where `heights[k] > h = max(heights[a], heights[b])`. We group these search queries by their `v` value into a map, `queriesByV`.

Next, we iterate backwards from `i = heights.length - 1` down to `0`. We use a monotonic stack that stores pairs `(height, index)`. This stack maintains a list of candidate buildings, where if `(h1, k1)` is below `(h2, k2)` in the stack, then `k1 > k2` and `h1 > h2`. 

In each iteration `i`:
1. We first process all queries that have `v = i`. For each of these queries, we search the current monotonic stack. The stack contains all optimal candidates with indices greater than `i`. We can use binary search on the stack's heights to find the best meeting place in `O(log N)` time.
2. Then, we update the stack with the building at index `i`. We pop elements from the stack that are shorter or equal in height to `heights[i]` because `i` would be a better or equal candidate for any future query. Finally, we push `(heights[i], i)` onto the stack.

This method processes each building and each query a constant number of times (plus the `log N` factor for search), leading to a much better time complexity.

```java
import java.util.*;

class Solution {
    public int[] canMeet(int[] heights, int[][] queries) {
        int n = heights.length;
        int q = queries.length;
        int[] ans = new int[q];
        Arrays.fill(ans, -1);

        List<int[]>[] queriesByV = new List[n];
        for (int i = 0; i < n; i++) {
            queriesByV[i] = new ArrayList<>();
        }

        for (int i = 0; i < q; i++) {
            int u = queries[i][0];
            int v = queries[i][1];

            if (u == v) {
                ans[i] = u;
                continue;
            }
            if (heights[u] < heights[v] && u < v) {
                ans[i] = v;
                continue;
            }
            if (heights[v] < heights[u] && v < u) {
                ans[i] = u;
                continue;
            }

            int startIdx = Math.max(u, v);
            int requiredHeight = Math.max(heights[u], heights[v]);
            queriesByV[startIdx].add(new int[]{requiredHeight, i});
        }

        List<int[]> stack = new ArrayList<>(); // Stores {height, index}

        for (int i = n - 1; i >= 0; i--) {
            // Process queries starting after i
            for (int[] query : queriesByV[i]) {
                int requiredHeight = query[0];
                int queryIndex = query[1];

                // Binary search on the stack for the first height > requiredHeight
                int low = 0, high = stack.size() - 1;
                int bestIdx = -1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (stack.get(mid)[0] > requiredHeight) {
                        bestIdx = stack.get(mid)[1];
                        low = mid + 1; // Try to find a smaller index (further right in stack)
                    } else {
                        high = mid - 1;
                    }
                }
                ans[queryIndex] = bestIdx;
            }

            // Update monotonic stack
            while (!stack.isEmpty() && stack.get(stack.size() - 1)[0] <= heights[i]) {
                stack.remove(stack.size() - 1);
            }
            stack.add(new int[]{heights[i], i});
        }

        return ans;
    }
}
```
### Algorithm
- **Preprocessing Queries**: 
  - Iterate through each query `[a, b]` with index `q_idx`.
  - Handle simple cases first: if `a == b`, the answer is `a`. If `heights[min(a,b)] < heights[max(a,b)]`, the answer is `max(a,b)`. Store these answers.
  - For the remaining complex queries, we need to find the smallest `k > v = max(a, b)` where `heights[k] > h = max(heights[a], heights[b])`. 
  - Group these complex queries by `v`. A map or an array of lists `queriesByV` can be used, where `queriesByV[v]` stores a list of `(h, q_idx)` pairs.
- **Main Loop with Monotonic Stack**:
  - Initialize an empty monotonic stack. The stack will store pairs of `(height, index)`.
  - Iterate `i` from `N-1` down to `0`.
  - **Process Queries**: For the current index `i`, process all queries where `v = i`. For each such query `(h, q_idx)`:
    - The stack currently contains candidate buildings `(h_j, j)` where `j > i`. The stack is maintained such that heights are strictly decreasing from bottom to top.
    - Perform a binary search on the stack to find the candidate `(h_j, j)` with the smallest index `j` such that `h_j > h`. This corresponds to the element at the largest valid index in the stack's underlying array.
    - If a suitable building is found, store its index `j` as the answer for `q_idx`. Otherwise, the answer remains -1.
  - **Update Stack**: After processing queries for `v=i`, update the stack with the current building `i`. Pop from the stack while its top element's height is less than or equal to `heights[i]`. Then, push `(heights[i], i)` onto the stack. This maintains the monotonic property.

# Solutions
### Java

```java
class BinaryIndexedTree { private final int inf = 1 << 30 ; private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; Arrays . fill ( c , inf ); } public void update ( int x , int v ) { while ( x <= n ) { c [ x ] = Math . min ( c [ x ], v ); x += x & - x ; } } public int query ( int x ) { int mi = inf ; while ( x > 0 ) { mi = Math . min ( mi , c [ x ]); x -= x & - x ; } return mi == inf ? - 1 : mi ; } } class Solution { public int [] leftmostBuildingQueries ( int [] heights , int [][] queries ) { int n = heights . length ; int m = queries . length ; for ( int i = 0 ; i < m ; ++ i ) { if ( queries [ i ][ 0 ] > queries [ i ][ 1 ]) { queries [ i ] = new int [] { queries [ i ][ 1 ], queries [ i ][ 0 ]}; } } Integer [] idx = new Integer [ m ]; for ( int i = 0 ; i < m ; ++ i ) { idx [ i ] = i ; } Arrays . sort ( idx , ( i , j ) -> queries [ j ][ 1 ] - queries [ i ][ 1 ]); int [] s = heights . clone (); Arrays . sort ( s ); int [] ans = new int [ m ]; int j = n - 1 ; BinaryIndexedTree tree = new BinaryIndexedTree ( n ); for ( int i : idx ) { int l = queries [ i ][ 0 ], r = queries [ i ][ 1 ]; while ( j > r ) { int k = n - Arrays . binarySearch ( s , heights [ j ]) + 1 ; tree . update ( k , j ); -- j ; } if ( l == r || heights [ l ] < heights [ r ]) { ans [ i ] = r ; } else { int k = n - Arrays . binarySearch ( s , heights [ l ]); ans [ i ] = tree . query ( k ); } } return ans ; } }
```

### CPP

```cpp
class BinaryIndexedTree { private: int inf = 1 << 30 ; int n ; vector < int > c ; public: BinaryIndexedTree ( int n ) { this -> n = n ; c . resize ( n + 1 , inf ); } void update ( int x , int v ) { while ( x <= n ) { c [ x ] = min ( c [ x ], v ); x += x & - x ; } } int query ( int x ) { int mi = inf ; while ( x > 0 ) { mi = min ( mi , c [ x ]); x -= x & - x ; } return mi == inf ? - 1 : mi ; } }; class Solution { public: vector < int > leftmostBuildingQueries ( vector < int >& heights , vector < vector < int >>& queries ) { int n = heights . size (), m = queries . size (); for ( auto & q : queries ) { if ( q [ 0 ] > q [ 1 ]) { swap ( q [ 0 ], q [ 1 ]); } } vector < int > idx ( m ); iota ( idx . begin (), idx . end (), 0 ); sort ( idx . begin (), idx . end (), [ & ]( int i , int j ) { return queries [ j ][ 1 ] < queries [ i ][ 1 ]; }); vector < int > s = heights ; sort ( s . begin (), s . end ()); s . erase ( unique ( s . begin (), s . end ()), s . end ()); vector < int > ans ( m ); int j = n - 1 ; BinaryIndexedTree tree ( n ); for ( int i : idx ) { int l = queries [ i ][ 0 ], r = queries [ i ][ 1 ]; while ( j > r ) { int k = s . end () - lower_bound ( s . begin (), s . end (), heights [ j ]) + 1 ; tree . update ( k , j ); -- j ; } if ( l == r || heights [ l ] < heights [ r ]) { ans [ i ] = r ; } else { int k = s . end () - lower_bound ( s . begin (), s . end (), heights [ l ]); ans [ i ] = tree . query ( k ); } } return ans ; } };
```

### Python

```python
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
```