LeetCode 2940 - Find Building Where Alice and Bob Can Meet

LeetCode Problem 2940

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Stack, Binary Indexed Tree, Segment Tree, Heap (Priority Queue), Monotonic Stack

Solution

Problem Understanding

You are given an array heights, where each index represents a building and the value represents that building's height. A person standing at building i can move only to the right, meaning to some building j where j > i, and only if the destination building is strictly taller, meaning heights[j] > heights[i].

Each query contains two starting positions, ai and bi, representing Alice's and Bob's initial buildings. For every query, we must determine the leftmost building index where both people can eventually meet.

A meeting building must satisfy the movement rules for both people. Since movement is only allowed toward the right and only to strictly taller buildings, a valid meeting point k must satisfy:

• k >= ai and k >= bi
• Alice can reach k
• Bob can reach k

The problem asks specifically for the leftmost valid meeting building. If no such building exists, we return -1.

There are several important observations hidden inside the movement rules.

If Alice and Bob already start at the same building, then the answer is immediately that building itself.

If one person is already at a building to the right of the other, and that building is taller than the left person's building, then the left person can directly move there. In that case, the answer is simply the farther building.

For all other cases, we must search for the first building to the right of both positions whose height exceeds both starting heights.

The constraints are large:

• heights.length <= 5 * 10^4
• queries.length <= 5 * 10^4

A naive solution that scans linearly for every query could become O(n * q), which is up to 2.5 * 10^9 operations and far too slow.

This immediately suggests that we need an efficient preprocessing or offline-query strategy.

Important edge cases include:

• Alice and Bob starting at the same building
• One person already being able to move directly to the other's building
• Queries where no taller building exists afterward
• Strictly decreasing height arrays
• Duplicate heights, since movement requires strictly greater height

Approaches

Brute Force Approach

The simplest approach is to process each query independently.

For a query [a, b], we first normalize the indices so that a <= b.

Several easy cases can be answered immediately:

• If a == b, answer is b
• If heights[a] < heights[b], Alice can directly move to Bob's building, so answer is b

Otherwise, we must search for the first index k > b such that:

heights[k] > heights[a]
and
heights[k] > heights[b]

We can scan linearly from b + 1 until we either find such a building or reach the end.

This works correctly because it explicitly checks every possible meeting point in left-to-right order. The first valid one is guaranteed to be the leftmost answer.

However, this approach is too slow. In the worst case, every query may scan nearly the entire array.

Key Insight for the Optimal Solution

The crucial observation is that difficult queries all reduce to the same form:

Find the first building to the right of index b whose height is greater than some threshold.

More specifically:

threshold = max(heights[a], heights[b])

We need the leftmost index k > b such that:

heights[k] > threshold

This becomes a classic offline-query problem.

We process buildings from right to left while maintaining a monotonic decreasing stack of candidate buildings. The stack stores indices whose heights are strictly decreasing.

Because the stack is monotonic, we can binary search inside it to find the first building taller than the threshold.

This reduces each query to logarithmic time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q * n)	O(1)	Scans rightward for every difficult query
Optimal	O((n + q) log n)	O(n + q)	Offline processing with monotonic stack and binary search

Algorithm Walkthrough

Optimal Offline Monotonic Stack Algorithm

1. First, initialize the answer array with -1 for all queries.
2. For every query [a, b], normalize the indices so that a <= b. This simplifies the logic because any meeting point must lie at or to the right of b.
3. Handle trivial cases immediately:

• If a == b, answer is b
• If heights[a] < heights[b], Alice can directly move to Bob's building, so answer is b

4. For all remaining queries, the problem becomes:

Find the leftmost index k > b such that:

heights[k] > heights[a]

Since we already know heights[a] >= heights[b], exceeding heights[a] automatically exceeds heights[b]. 5. Group deferred queries by their right endpoint b. For every query that still needs processing, store:

• the required height threshold
• the query index

6. Process the buildings from right to left.
7. Maintain a monotonic decreasing stack of building indices.

The stack invariant is:

heights[stack[0]] > heights[stack[1]] > heights[stack[2]] ...

Before inserting a new building index i, remove all smaller or equal heights from the top. 8. When processing index i, answer all queries whose b == i.

For each query, binary search the stack to find the smallest index whose height exceeds the threshold. 9. Because the stack stores candidate buildings in increasing positional order from bottom to top, the binary search identifies the leftmost valid building. 10. Store the result into the answer array.

Why it works

The stack always contains buildings to the right of the current position, and its heights are strictly decreasing. Any building removed from the stack is dominated by a taller building closer to the left, so it can never become the leftmost valid answer for future queries.

When we binary search the stack for a height greater than the threshold, we are guaranteed to find the earliest reachable building satisfying the movement condition. Since queries are processed exactly when all buildings to their right have already been inserted, no valid candidate is missed.

Python Solution

from typing import List
from bisect import bisect_right

class Solution:
    def leftmostBuildingQueries(
        self,
        heights: List[int],
        queries: List[List[int]]
    ) -> List[int]:

        n = len(heights)
        q = len(queries)

        answers = [-1] * q

        deferred = [[] for _ in range(n)]

        for query_index, (a, b) in enumerate(queries):

            if a > b:
                a, b = b, a

            if a == b:
                answers[query_index] = b

            elif heights[a] < heights[b]:
                answers[query_index] = b

            else:
                deferred[b].append((heights[a], query_index))

        stack = []

        for i in range(n - 1, -1, -1):

            while stack and heights[stack[-1]] <= heights[i]:
                stack.pop()

            stack.append(i)

            for required_height, query_index in deferred[i]:

                left = 0
                right = len(stack) - 1

                answer = -1

                while left <= right:

                    mid = (left + right) // 2

                    if heights[stack[mid]] > required_height:
                        answer = stack[mid]
                        left = mid + 1
                    else:
                        right = mid - 1

                answers[query_index] = answer

        return answers

Implementation Explanation

The solution begins by preparing an answer array initialized to -1.

We normalize each query so that a <= b. This guarantees that any future meeting building must lie at or after index b.

The two trivial cases are handled immediately:

• Same starting building
• Alice can directly move to Bob's building

All remaining queries are stored in deferred[b]. Each deferred query only needs to know:

• the required height threshold
• the original query index

The main loop processes buildings from right to left.

The monotonic stack stores indices with strictly decreasing heights. Before adding a building, all smaller or equal heights are removed because they can never provide a better answer than the current building.

When handling deferred queries for index i, we binary search the stack for the farthest valid stack position whose height exceeds the threshold. Due to the stack ordering, this corresponds to the leftmost valid building index.

Go Solution

package main

func leftmostBuildingQueries(heights []int, queries [][]int) []int {

	n := len(heights)
	q := len(queries)

	ans := make([]int, q)

	for i := 0; i < q; i++ {
		ans[i] = -1
	}

	type Query struct {
		height int
		index  int
	}

	deferred := make([][]Query, n)

	for i, query := range queries {

		a := query[0]
		b := query[1]

		if a > b {
			a, b = b, a
		}

		if a == b {
			ans[i] = b
		} else if heights[a] < heights[b] {
			ans[i] = b
		} else {
			deferred[b] = append(
				deferred[b],
				Query{
					height: heights[a],
					index:  i,
				},
			)
		}
	}

	stack := []int{}

	for i := n - 1; i >= 0; i-- {

		for len(stack) > 0 &&
			heights[stack[len(stack)-1]] <= heights[i] {

			stack = stack[:len(stack)-1]
		}

		stack = append(stack, i)

		for _, query := range deferred[i] {

			requiredHeight := query.height

			left := 0
			right := len(stack) - 1

			answer := -1

			for left <= right {

				mid := (left + right) / 2

				if heights[stack[mid]] > requiredHeight {
					answer = stack[mid]
					left = mid + 1
				} else {
					right = mid - 1
				}
			}

			ans[query.index] = answer
		}
	}

	return ans
}

Go-specific Notes

The Go implementation follows the same logic as the Python solution.

Slices are used for both the monotonic stack and deferred query lists. Since Go does not provide a built-in binary search customized for this structure, the binary search is implemented manually.

All integer operations remain safe because indices and heights stay within standard 32-bit integer ranges.

Unlike Python, Go requires explicit struct definitions for storing deferred query information.

Worked Examples

Example 1

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

Step 1: Process Queries

Query	Normalized	Immediate Answer?	Deferred Condition
[0,1]	[0,1]	No	Find height > 6 after index 1
[0,3]	[0,3]	No	Find height > 6 after index 3
[2,4]	[2,4]	No	Find height > 8 after index 4
[3,4]	[3,4]	No	Find height > 5 after index 4
[2,2]	[2,2]	Yes, answer = 2	None

Step 2: Traverse from Right to Left

i	Height	Stack After Update	Queries Processed	Answer
5	7	[5]	None	None
4	2	[5,4]	>8, >5	5 for >5
3	5	[5,3]	>6	5
2	8	[2]	None	None
1	4	[2,1]	>6	2
0	6	[2,0]	None	None

Final answers:

[2,5,-1,5,2]

Example 2

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

Step 1: Immediate Cases

Query	Result
[0,7]	7
[1,6]	6

Deferred Queries

Query	Need
[3,5]	First height > 2 after index 5
[5,2]	First height > 8 after index 5
[3,0]	First height > 5 after index 3

Reverse Traversal

i	Stack	Processed Queries	Result
7	[7]	None	None
6	[7,6]	None	None
5	[7,6,5]	>2, >8	6, -1
4	[7,4]	None	None
3	[7,4,3]	>5	4

Final answers:

[7,6,-1,4,6]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + q) log n)	Each query performs one binary search
Space	O(n + q)	Stack plus deferred query storage

The monotonic stack operations are amortized O(n) because every building index is pushed and popped at most once.

Each deferred query performs a binary search on the stack, costing O(log n).

Therefore, the total complexity becomes:

O(n + q log n)

which easily fits the problem constraints.

Test Cases

sol = Solution()

# Provided example 1
assert sol.leftmostBuildingQueries(
    [6,4,8,5,2,7],
    [[0,1],[0,3],[2,4],[3,4],[2,2]]
) == [2,5,-1,5,2]

# Provided example 2
assert sol.leftmostBuildingQueries(
    [5,3,8,2,6,1,4,6],
    [[0,7],[3,5],[5,2],[3,0],[1,6]]
) == [7,6,-1,4,6]

# Same starting building
assert sol.leftmostBuildingQueries(
    [1,2,3],
    [[1,1]]
) == [1]

# Strictly increasing heights
assert sol.leftmostBuildingQueries(
    [1,2,3,4,5],
    [[0,1],[1,2],[2,4]]
) == [1,2,4]

# Strictly decreasing heights
assert sol.leftmostBuildingQueries(
    [5,4,3,2,1],
    [[0,1],[1,2],[2,4]]
) == [-1,-1,-1]

# Duplicate heights
assert sol.leftmostBuildingQueries(
    [4,4,4,4],
    [[0,1],[1,2]]
) == [-1,-1]

# Meeting at a later taller building
assert sol.leftmostBuildingQueries(
    [3,1,2,5],
    [[0,1],[1,2]]
) == [3,2]

# Single building array
assert sol.leftmostBuildingQueries(
    [10],
    [[0,0]]
) == [0]

# Larger mixed case
assert sol.leftmostBuildingQueries(
    [2,7,1,8,3,9,4],
    [[0,2],[2,4],[1,6]]
) == [1,5,-1]

# No possible meeting point
assert sol.leftmostBuildingQueries(
    [9,8,7,6,5],
    [[0,4],[1,3]]
) == [-1,-1]

Test Case Summary

Test	Why
Provided examples	Validates correctness against official outputs
Same starting building	Ensures trivial self-meeting case works
Strictly increasing heights	Tests direct movement behavior
Strictly decreasing heights	Tests impossible meeting scenarios
Duplicate heights	Verifies strict inequality handling
Later taller building	Tests deferred query logic
Single building	Validates minimum input size
Mixed heights	Tests general correctness
No meeting possible	Ensures -1 handling

Edge Cases

Same Starting Position

If Alice and Bob begin at the same building, the answer must immediately be that index. A buggy implementation might unnecessarily search for another meeting point or fail to recognize that no movement is needed.

The implementation explicitly checks:

if a == b:
    answers[query_index] = b

This guarantees correct handling in constant time.

Equal Heights

Movement requires strictly greater height. Two buildings with the same height are not reachable from one another.

For example:

heights = [4,4,4]

No person can move anywhere.

This is especially important inside the monotonic stack maintenance step. The implementation removes buildings using:

while heights[stack[-1]] <= heights[i]:

The <= is critical. If only < were used, equal-height buildings would incorrectly remain as valid candidates.

No Valid Meeting Building

Some queries have no possible meeting point because no sufficiently tall building exists to the right.

Example:

heights = [9,8,7,6]
query = [0,1]

No building taller than 9 exists afterward.

The implementation initializes answers with -1 and only overwrites them when a valid building is found. This naturally handles impossible cases correctly.

Direct Reachability

If the left person's building is shorter than the right person's building, the left person can directly move there.

Example:

heights = [2,5]
query = [0,1]

Answer is immediately 1.

Without this optimization, the algorithm might incorrectly continue searching for another building farther right, violating the requirement for the leftmost meeting point.