Find Building Where Alice and Bob Can Meet

Find Building Where Alice and Bob Can Meet - Problem

Array Binary Search Stack Binary Indexed Tree Segment Tree Heap (Priority Queue) Monotonic Stack Hard

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

You are also given another array queries where queries[i] = [a_i, b_i]. On the i-th query, Alice is in building a_i while Bob is in building b_i.

Return an array ans where ans[i] is the index of the leftmost building where Alice and Bob can meet on the i-th query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.

Input & Output

Example 1 — Basic Meeting

$ Input: heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]

› Output: [2,5,-1,-1,2]

💡 Note: Query [0,1]: Alice at 6, Bob at 4. First building both can reach is index 2 (height 8). Query [0,3]: Alice needs height > 6, Bob needs > 5, first such building is index 5 (height 7). Query [2,4]: Alice at 8, Bob at 2, but no building after index 4 is taller than 8. Query [3,4]: Bob at 2, Alice at 5, no building after index 4 is taller than 5. Query [2,2]: Same position, return 2.

Example 2 — Direct Reach

$ Input: heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[2,6]]

› Output: [7,5,2]

💡 Note: Query [0,7]: Alice at height 5, Bob at height 6. Since Bob's building (index 7) is to the right and taller than Alice's, they can meet at index 7. Query [3,5]: Alice at height 2, Bob at height 1. Alice can reach Bob's position since index 5 > 3 and height 1 < 2 is false, but 6 > 2, so answer is 5. Query [2,6]: Alice already at height 8, Bob at height 4, Alice's position works.

Example 3 — No Meeting Possible

$ Input: heights = [1,2,1,2], queries = [[0,0],[1,3]]

› Output: [0,-1]

💡 Note: Query [0,0]: Same building, return 0. Query [1,3]: Alice at height 2 (index 1), Bob at height 2 (index 3). No building after index 3 exists, so they cannot meet at a common taller building.

Constraints

1 ≤ heights.length ≤ 5 × 10⁴
1 ≤ heights[i] ≤ 10⁹
1 ≤ queries.length ≤ 5 × 10⁴
queries[i] = [a_i, b_i]
0 ≤ a_i, b_i ≤ heights.length - 1

Visualization

Tap to expand

Understanding the Visualization

Input Buildings

Array of building heights with Alice and Bob at specific positions

Movement Rules

Can only move right to taller buildings (i < j and heights[i] < heights[j])

Find Meeting

Leftmost building both can reach, or -1 if impossible

Key Takeaway

🎯 Key Insight: Find the leftmost building that is taller than both starting positions and has an index greater than both

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that people can only move to taller buildings with higher indices. For each query, check if one person can reach the other's building directly, otherwise find the leftmost building both can reach. Best approach uses brute force with optimizations for direct reachability checks. Time: O(q × n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack with Binary Search	O(n + q log n)	O(n)	Use monotonic stack to precompute reachable buildings and binary search for efficient queries
Brute Force	O(q × n)	O(1)	For each query, check all buildings to the right until finding a common meeting point

Monotonic Stack with Binary Search — Algorithm Steps

Build a monotonic decreasing stack to find next greater elements
For each query, determine the minimum height needed for meeting
Use binary search to find leftmost building with sufficient height
Handle special cases where one person can reach the other's building

Visualization

Tap to expand

Step-by-Step Walkthrough

Analyze Query

Check if one person can reach the other directly

Find Minimum

Determine minimum height needed for meeting

Quick Scan

Find first building exceeding minimum height

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* heights, int heightsSize, int** queries, int queriesSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int q = 0; q < queriesSize; q++) {
        int a = queries[q][0], b = queries[q][1];
        
        // If same building
        if (a == b) {
            result[q] = a;
            continue;
        }
        
        // Ensure a <= b for consistency
        if (a > b) {
            int temp = a; a = b; b = temp;
        }
        
        // If b is reachable from a
        if (heights[b] > heights[a]) {
            result[q] = b;
            continue;
        }
        
        // Need to find leftmost building both can reach
        int minHeight = (heights[a] > heights[b]) ? heights[a] : heights[b];
        int found = 0;
        
        for (int i = b + 1; i < heightsSize; i++) {
            if (heights[i] > minHeight) {
                result[q] = i;
                found = 1;
                break;
            }
        }
        
        if (!found) {
            result[q] = -1;
        }
    }
    
    return result;
}

int main() {
    // Simple parsing for demonstration
    int heights[] = {6, 4, 8, 5, 2, 7};
    int heightsSize = 6;
    
    int query1[] = {0, 1};
    int query2[] = {0, 3};
    int* queries[] = {query1, query2};
    int queriesSize = 2;
    
    int returnSize;
    int* result = solution(heights, heightsSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + q log n)

O(n) to build stack preprocessing, O(log n) binary search per query

⚡ Linearithmic

Space Complexity

O(n)

Stack and auxiliary arrays for preprocessing

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack with Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler