⚡Flashcard Drill➔
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

  1. Reduce each query to: given a starting index b = max(a, b) and a required height h = max(heights[a], heights[b]), find the smallest c > b with heights[c] > h.
  2. Process the queries offline, grouped by b in descending order, so the set of candidate indices > b grows as b decreases.
  3. 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.
  4. Because the stack's heights decrease with the list position, the last entry taller than h has 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 b for 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 as b decreases.
  • 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 == b or heights[b] > heights[a], the answer is b directly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems