3181. Find Building Where Alice and Bob Can Meet
My accepted Python solution to LeetCode problem 3181, Find Building Where Alice and Bob Can Meet, running in 526ms.
- Difficulty: Hard
- Python
- Runtime 526ms
- Memory 48.5MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 526ms, memory 48.5MB, accepted 2026-01-01.
class Solution:
def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
n = len(heights)
q = len(queries)
result = [-1] * q
# Group queries by the rightmost index
deferred = [[] for _ in range(n)]
for i, (a, b) in enumerate(queries):
if a > b:
a, b = b, a
# If already at same building, or can move directly
if a == b:
result[i] = a
elif heights[a] < heights[b]:
result[i] = b
else:
# Need to find j > b where heights[j] > max(heights[a], heights[b])
deferred[b].append((max(heights[a], heights[b]), i))
# Use monotonic stack to answer deferred queries
stack = [] # (height, index)
for i in range(n - 1, -1, -1):
# Process deferred queries at position i
for height_needed, query_idx in deferred[i]:
# Binary search for smallest index in stack with height > height_needed
lo, hi = 0, len(stack) - 1
ans_idx = -1
while lo <= hi:
mid = (lo + hi) // 2
if stack[mid][0] > height_needed:
ans_idx = stack[mid][1]
lo = mid + 1
else:
hi = mid - 1
result[query_idx] = ans_idx
# Maintain monotonic decreasing stack
while stack and stack[-1][0] <= heights[i]:
stack.pop()
stack.append((heights[i], i))
return result