> ## Documentation Index > Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt > Use this file to discover all available pages before exploring further. > ## Agent Instructions > leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform. > Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package. > Examples are backed by tests; copy them verbatim. # Find Building Where Alice and Bob Can Meet > Tested Python solution for LeetCode 2940 with 18 pytest cases. Generate a practice environment with lcpy. LeetCode 2940, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Binary Search](/catalog/topics/binary-search), [Stack](/catalog/topics/stack), [Binary Indexed Tree](/catalog/topics/binary-indexed-tree), [Segment Tree](/catalog/topics/segment-tree), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Monotonic Stack](/catalog/topics/monotonic-stack). [View on LeetCode](https://leetcode.com/problems/find-building-where-alice-and-bob-can-meet/description/). Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook: ```bash theme={"theme":{"light":"github-light","dark":"github-dark"}} lcpy gen -n 2940 # by problem number lcpy gen -s find_building_where_alice_and_bob_can_meet # by problem name ``` ## Problem You are given a **0-indexed** array `heights` of positive integers, where `heights[i]` represents the height of the `i`th 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]`. You are also given another array `queries` where `queries[i] = [a_i, b_i]`. On the `i`th query, Alice is in building `a_i` while Bob is in building `b_i`. Return *an array* `ans` where `ans[i]` is **the index of the leftmost building** where Alice and Bob can meet on the `i`th query. If Alice and Bob cannot move to a common building on query `i`, set `ans[i]` to `-1`. ### Examples ``` 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]. In the second query, Alice and Bob can move to building 5 since heights[0] < heights[5] and heights[3] < heights[5]. In the third query, Alice cannot meet Bob since Alice cannot move to any other building. In the fourth query, Alice and Bob can move to building 5 since heights[3] < heights[5] and heights[4] < heights[5]. In the fifth query, Alice and Bob are already in the same building. For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet. For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet. ``` ``` Input: heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]] Output: [7,6,-1,4,6] Explanation: In the first query, Alice can directly move to Bob's building since heights[0] < heights[7]. In the second query, Alice and Bob can move to building 6 since heights[3] < heights[6] and heights[5] < heights[6]. In the third query, Alice cannot meet Bob since Bob cannot move to any other building. In the fourth query, Alice and Bob can move to building 4 since heights[3] < heights[4] and heights[0] < heights[4]. In the fifth query, Alice can directly move to Bob's building since heights[1] < heights[6]. For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet. For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet. ``` ### Constraints * 1 \<= heights.length \<= 5 \* 10^4 * 1 \<= heights\[i] \<= 10^9 * 1 \<= queries.length \<= 5 \* 10^4 * queries\[i] = \[a\_i, b\_i] * 0 \<= a\_i, b\_i \<= heights.length - 1 ## Solution Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_building_where_alice_and_bob_can_meet/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_building_where_alice_and_bob_can_meet/test_solution.py): ```python theme={"theme":{"light":"github-light","dark":"github-dark"}} class Solution: # Time: O((n + q) log n) - one build pass over the tree plus a descent per query # Space: O(n) - segment tree over the building heights def leftmost_building_queries(self, heights: list[int], queries: list[list[int]]) -> list[int]: n = len(heights) size = 1 while size < n: size <<= 1 tree = [0] * (2 * size) tree[size : size + n] = heights for i in range(size - 1, 0, -1): tree[i] = max(tree[2 * i], tree[2 * i + 1]) def next_greater(start: int, limit: int) -> int: def descend(node: int, node_lo: int, node_hi: int) -> int: if node_hi <= start or tree[node] <= limit: return -1 if node_lo == node_hi: return node_lo mid = (node_lo + node_hi) // 2 found = descend(2 * node, node_lo, mid) return found if found != -1 else descend(2 * node + 1, mid + 1, node_hi) if start >= n: return -1 return descend(1, 0, size - 1) result: list[int] = [] for query in queries: left, right = query[0], query[1] if left > right: left, right = right, left if left == right: result.append(left) elif heights[left] < heights[right]: result.append(right) else: result.append(next_greater(right, heights[left])) return result ``` ## Complexity | Time | Space | | - | - | | O((n + q) log n) - one build pass over the tree plus a descent per query | O(n) - segment tree over the building heights | ## Tags [NeetCode All](/catalog/neetcode). This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.