Skip to main content
Talentd

Find Building Where Alice and Bob Can Meet - Solution & Explanation

HardArrayBinary SearchStackBinary Indexed Tree20 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given building heights and multiple queries. Each query contains two starting buildings for Alice and Bob. They can only move to the right and only to a building with a strictly greater height. The goal is to return the leftmost building index where both can meet, or -1 if no such building exists.

Approach 1: Next Greater Element Precomputation (O((n+q) log n) time, O(n log n) space)

The movement rule is identical to the classic next greater element pattern. From any building i, the next possible move is the first index to the right with a greater height. Compute this using a monotonic stack in O(n). This forms a directed chain of valid jumps.

For each query (a, b), normalize so a ≤ b. If heights[a] < heights[b], they can meet directly at b. Otherwise, Bob cannot move left, so the answer must be some building to the right of b with height greater than heights[a]. Using the precomputed next-greater links, build binary lifting jump pointers so you can quickly skip through the chain until you find the first building taller than heights[a]. Each query becomes a logarithmic search over the jump table.

This approach works well because the next-greater structure compresses all valid moves into a monotonic chain. Instead of scanning linearly, you jump across increasing heights using precomputed powers of two.

Approach 2: Binary Search on Preprocessed Data (O((n+q) log n) time, O(n) space)

Another strategy processes buildings while maintaining a decreasing stack of candidate indices. The stack represents buildings that could serve as the next taller building for future positions. As you scan from right to left, you remove shorter buildings and maintain a monotonic structure similar to the classic stack next-greater algorithm.

For each query where a ≤ b and heights[a] ≥ heights[b], the meeting building must be to the right of b and must exceed heights[a]. The candidate stack to the right of b is strictly increasing in height, so you can apply binary search to locate the first building whose height is greater than heights[a]. Preprocessing ensures the candidate list remains ordered, making each lookup logarithmic.

This method avoids jump pointers and instead relies on the monotonic property of the stack. Binary search quickly identifies the first valid meeting building.

Recommended for interviews: The monotonic stack preprocessing combined with logarithmic queries is typically expected. It demonstrates understanding of next greater element patterns and efficient query handling. Starting with the brute-force idea (scan to the right for every query) shows the intuition, but the optimized approach using stack-based preprocessing and binary search shows strong algorithmic maturity.

Approach 1: Precompute the Next Greater Element

This approach involves preprocessing the heights array to identify each building's nearest potential building with greater height. For each query, you can then quickly determine the first such building where both Alice and Bob can move. This significantly reduces unnecessary repeated calculations for multiple queries.

The code first computes the next greater elements for each building using a stack-based approach. The idea is to find the minimum index of the next taller building for each query, where both Alice and Bob can meet. If such a building doesn't exist, the result for that query is -1.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + q), where n is the number of buildings and q is the number of queries.
Space Complexity: O(n) for storing the next greater elements.

Try this approach in the editor →

Approach 2: Binary Search on Preprocessed Data

Another approach is to store a list of building heights and their indices and utilize binary searching techniques to efficiently find the first building both Alice and Bob can move to. This approach prioritizes efficient query handling by using sorted data structures.

The C solution preprocesses the building indexes based on their heights for efficient query handling. It then uses binary search to find potential meeting points for each query.

Code

C

C

Complexity

Time Complexity: O(n log n + q log n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: 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].

We can sort queries in descending order of r_i, and use a pointer j to point to the current index of heights being traversed.

Next, we traverse each query queries[i] = (l, r). For the current query, if j > r, then we loop to insert heights[j] into the binary indexed tree. The binary indexed tree maintains the minimum index of the suffix height (after discretization). Then, we judge whether l = r or heights[l] < heights[r]. If it is, then the answer to the current query is r. Otherwise, we query the minimum index of heights[l] in the binary indexed tree, which is the answer to the current query.

The time complexity is O((n + m) times log n + m times log m), and the space complexity is O(n + m). Where n and m are the lengths of heights and queries respectively.

Similar problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Precompute the Next Greater Element

Time Complexity: O(n + q), where n is the number of buildings and q is the number of queries.
Space Complexity: O(n) for storing the next greater elements.

Binary Search on Preprocessed Data

Time Complexity: O(n log n + q log n)
Space Complexity: O(n)

Binary Indexed Tree—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ScanO(n * q)O(1)Useful for understanding the movement rule before optimization
Next Greater Element + Binary LiftingO((n+q) log n)O(n log n)Efficient for many queries and direct navigation along next-greater chains
Monotonic Stack + Binary SearchO((n+q) log n)O(n)Cleaner implementation when maintaining ordered candidate buildings

Video Solution

Find Building Where Alice and Bob Can Meet - Leetcode 2940 - Python • NeetCodeIO • 13,453 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Building Where Alice and Bob Can Meet easy or hard?
The problem is rated Hard because it combines multiple concepts: monotonic stacks, query normalization, and efficient searching for the next valid building. The core next-greater idea is straightforward, but integrating it with fast query handling makes the problem challenging.
Find Building Where Alice and Bob Can Meet Python/Java solution
Python and Java implementations typically compute the next greater element array using a stack, then process queries using binary search or jump pointers. The preprocessing step is O(n), and each query is answered in O(log n) time, making the solution efficient for large inputs.
What is the best approach for Find Building Where Alice and Bob Can Meet?
The most common solution uses a monotonic stack to preprocess next greater buildings and then answers queries with logarithmic search. After normalizing each query so the left index comes first, the algorithm checks direct meeting conditions and otherwise searches for the first building to the right that exceeds the required height. This reduces query processing to O(log n).
How to solve Find Building Where Alice and Bob Can Meet in O((n+q) log n)?
Precompute next greater elements using a monotonic decreasing stack. For each query (a, b), ensure a ≤ b. If heights[a] < heights[b], they meet at b. Otherwise search to the right of b for the first building with height greater than heights[a], using binary search over a preprocessed candidate list or binary lifting over the next-greater chain.
Is Find Building Where Alice and Bob Can Meet asked at Google/Amazon/Meta?
Problems involving next greater elements, monotonic stacks, and query preprocessing are common in interviews at companies like Google, Amazon, and Meta. Variants of this problem test your ability to combine stack-based preprocessing with efficient query handling.
What data structure is used in Find Building Where Alice and Bob Can Meet?
The core data structure is a monotonic stack used to compute next greater elements. Some implementations also use binary lifting tables, segment trees, heaps, or binary search structures to answer queries efficiently after preprocessing.
What is the time complexity of Find Building Where Alice and Bob Can Meet?
The optimized solutions run in O((n + q) log n) time. Building the monotonic stack or next greater element structure takes O(n), and each query requires a logarithmic search or jump through preprocessed data. Space complexity ranges from O(n) to O(n log n) depending on whether binary lifting tables are used.

Ready to solve this problem?

Practice Find Building Where Alice and Bob Can Meet with our built-in code editor and test cases.

Practice on FleetCode
Previous

Furthest Building You Can Reach

Next

Number of Visible People in a Queue