NeetCode #555LC-2940HardHeap / Priority Queue
← Back to All Problems#555 · #2940 · Find Building Where Alice and Bob Can Meet(找到 Alice 和 Bob 可以相遇的建筑)
📌 Problem Statement & Constraints
You are given an array
heights and queries where queries[i] = [a, b]. For each query, find the leftmost index c such that max(a, b) < c and heights[c] > max(heights[a], heights[b]). If a == b or heights[max(a,b)] > heights[min(a,b)], the answer is max(a, b). Return -1 when no such index exists. Constraints: 1 <= heights.length, queries.length <= 5 * 10^4.💡 Core Algorithmic Approaches
- Reduce each query to: given a starting index
b = max(a, b)and a required heighth = max(heights[a], heights[b]), find the smallestc > bwithheights[c] > h. - Process the queries offline, grouped by
bin descending order, so the set of candidate indices> bgrows asbdecreases. - Maintain a monotonic stack of indices with strictly decreasing heights: when a new index is added, pop everything not taller than it, since those can never be the leftmost answer.
- Because the stack's heights decrease with the list position, the last entry taller than
hhas the smallest index -- find it by binary search.
💻 Benchmark Python3 Implementation
class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
n = len(heights)
grouped = [[] for _ in range(n)] # b -> [(required height, query index)]
res = [-1] * len(queries)
for qi, (a, b) in enumerate(queries):
if a > b:
a, b = b, a
if a == b or heights[b] > heights[a]:
res[qi] = b # already satisfied
else:
grouped[b].append((heights[a], qi))
st = [] # indices, strictly decreasing heights
for i in range(n - 1, -1, -1):
# answer the queries whose right endpoint is i
for h, qi in grouped[i]:
# find the LAST stack position with height > h (-> smallest index)
lo, hi = 0, len(st)
while lo < hi:
mid = (lo + hi) // 2
if heights[st[mid]] > h:
lo = mid + 1
else:
hi = mid
if lo > 0:
res[qi] = st[lo - 1]
# push i, keeping the stack decreasing in height
while st and heights[st[-1]] <= heights[i]:
st.pop()
st.append(i)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + q) log n): each query costs a binary search over the stack.
💾 Space Complexity
O(n + q) for the grouping and the stack.
⚠️ Interview Pitfalls & Follow-ups
- Scanning forward from
bfor every query: O(n * q). - Building the monotonic stack over the whole array once: the candidates depend on
b, so the stack must be built incrementally asbdecreases. - Searching for the first stack position with height > h: because heights decrease with list position, the last such position gives the smallest index.
- Forgetting the early-answer case: when
a == borheights[b] > heights[a], the answer isbdirectly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.