3181 Find Building Where Alice And Bob Can Meet
3181 Find Building Where Alice And Bob Can Meet
Find Building Where Alice and Bob Can Meet 
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].
You are also given another array queries where queries[i] = [ai, bi]. On the ith query, Alice is in building ai while Bob is in building bi.
Return an array ans where ans[i] is the index of the leftmost building where Alice and Bob can meet on the ith query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.
Example 1:
1
2
3
4
5
6
7
8
9
10
11
**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.
Example 2:
1
2
3
4
5
6
7
8
9
10
11
**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
2
3
4
5
1 <= heights.length <= 5 * 104
1 <= heights[i] <= 109
1 <= queries.length <= 5 * 104
queries[i] = [ai, bi]
0 <= ai, bi <= heights.length - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
def leftmostBuildingQueries(self, heights, queries):
mono_stack = []
result = [-1 for _ in range(len(queries))]
new_queries = [[] for _ in range(len(heights))]
for i in range(len(queries)):
a = queries[i][0]
b = queries[i][1]
if a > b:
a, b = b, a
if heights[b] > heights[a] or a == b:
result[i] = b
else:
new_queries[b].append((heights[a], i))
for i in range(len(heights) - 1, -1, -1):
mono_stack_size = len(mono_stack)
for a, b in new_queries[i]:
position = self.search(a, mono_stack)
if position < mono_stack_size and position >= 0:
result[b] = mono_stack[position][1]
while mono_stack and mono_stack[-1][0] <= heights[i]:
mono_stack.pop()
mono_stack.append((heights[i], i))
return result
def search(self, height, mono_stack):
left = 0
right = len(mono_stack) - 1
ans = -1
while left <= right:
mid = (left + right) // 2
if mono_stack[mid][0] > height:
ans = max(ans, mid)
left = mid + 1
else:
right = mid - 1
return ans
This post is licensed under CC BY 4.0 by the author.