Find Building Where Alice and Bob Can Meet — LeetCode 2940 Python Solution
HardStackBinary Indexed TreeSegment TreeArrayBinary SearchMonotonic StackHeap (Priority Queue)
- Problem
- #2940
- Pattern
- Heap / Priority Queue
- Reading time
- 8 min
- Source
- leetcode.com
The problem
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].
Example
- 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].
Python solution
Python
class BinaryIndexedTree:
__slots__ = ["n", "c"]
def __init__(self, n: int):
self.n = n
self.c = [inf] * (n + 1)
def update(self, x: int, v: int):
while x <= self.n:
self.c[x] = min(self.c[x], v)
x += x & -x
def query(self, x: int) -> int:
mi = inf
while x:
mi = min(mi, self.c[x])
x -= x & -x
return -1 if mi == inf else mi
class Solution:
def leftmostBuildingQueries(
self, heights: List[int], queries: List[List[int]]
) -> List[int]:
n, m = len(heights), len(queries)
for i in range(m):
queries[i] = [min(queries[i]), max(queries[i])]
j = n - 1
s = sorted(set(heights))
ans = [-1] * m
tree = BinaryIndexedTree(n)
for i in sorted(range(m), key=lambda i: -queries[i][1]):
l, r = queries[i]
while j > r:
k = n - bisect_left(s, heights[j]) + 1
tree.update(k, j)
j -= 1
if l == r or heights[l] < heights[r]:
ans[i] = r
else:
k = n - bisect_left(s, heights[l])
ans[i] = tree.query(k)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O((n + m) \times \log n + m \times \log m) |
| Space | O(n + m) auxiliary |
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2940. Find Building Where Alice and Bob Can Meet is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2940. Find Building Where Alice and Bob Can Meet?
- LeetCode 2940. Find Building Where Alice and Bob Can Meet is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2940. Find Building Where Alice and Bob Can Meet?
- The Python solution on this page runs in O((n + m) \times \log n + m \times \log m).
- What is the space complexity of LeetCode 2940. Find Building Where Alice and Bob Can Meet?
- The Python solution on this page uses O(n + m) auxiliary space.
- What topics does LeetCode 2940. Find Building Where Alice and Bob Can Meet cover?
- LeetCode 2940. Find Building Where Alice and Bob Can Meet is tagged Stack, Binary Indexed Tree, Segment Tree, Array, Binary Search, Monotonic Stack and Heap (Priority Queue) on LeetCode.