2940. Find Building Where Alice and Bob Can Meet LeetCode Solution
In this guide, you will get 2940. Find Building Where Alice and Bob Can Meet LeetCode Solution with the best time and space complexity. The solution to Find Building Where Alice and Bob Can Meet problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Find Building Where Alice and Bob Can Meet solution in C++
- Find Building Where Alice and Bob Can Meet solution in Java
- Find Building Where Alice and Bob Can Meet solution in Python
- Additional Resources
Problem Statement of 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:
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:
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 * 104
1 <= heights[i] <= 109
1 <= queries.length <= 5 * 104
queries[i] = [ai, bi]
0 <= ai, bi <= heights.length – 1
Complexity Analysis
- Time Complexity: O(\texttt{sort}(q) + (q + n)\log n)
- Space Complexity: O(n + q)
2940. Find Building Where Alice and Bob Can Meet LeetCode Solution in C++
struct IndexedQuery {
int queryIndex;
int a; // Alice's index
int b; // Bob's index
};
class Solution {
public:
// Similar to 2736. Maximum Sum Queries
vector<int> leftmostBuildingQueries(vector<int>& heights,
vector<vector<int>>& queries) {
vector<int> ans(queries.size(), -1);
// Store indices (heightsIndex) of heights with heights[heightsIndex] in
// descending order.
vector<int> stack;
// Iterate through queries and heights simultaneously.
int heightsIndex = heights.size() - 1;
for (const auto& [queryIndex, a, b] : getIndexedQueries(queries)) {
if (a == b || heights[a] < heights[b]) {
// 1. Alice and Bob are already in the same index (a == b) or
// 2. Alice can jump from a -> b (heights[a] < heights[b]).
ans[queryIndex] = b;
} else {
// Now, a < b and heights[a] >= heights[b].
// Gradually add heights with an index > b to the monotonic stack.
while (heightsIndex > b) {
// heights[heightsIndex] is a better candidate, given that
// heightsIndex is smaller than the indices in the stack and
// heights[heightsIndex] is larger or equal to the heights mapped in
// the stack.
while (!stack.empty() &&
heights[stack.back()] <= heights[heightsIndex])
stack.pop_back();
stack.push_back(heightsIndex--);
}
// Binary search to find the smallest index j such that j > b and
// heights[j] > heights[a], thereby ensuring heights[j] > heights[b].
if (const auto it = upper_bound(
stack.rbegin(), stack.rend(), a,
[&](int a, int b) { return heights[a] < heights[b]; });
it != stack.rend())
ans[queryIndex] = *it;
}
}
return ans;
}
private:
vector<IndexedQuery> getIndexedQueries(const vector<vector<int>>& queries) {
vector<IndexedQuery> indexedQueries;
for (int i = 0; i < queries.size(); ++i) {
// Make sure that a <= b.
const int a = min(queries[i][0], queries[i][1]);
const int b = max(queries[i][0], queries[i][1]);
indexedQueries.push_back({i, a, b});
}
ranges::sort(
indexedQueries,
[](const IndexedQuery& a, const IndexedQuery& b) { return a.b > b.b; });
return indexedQueries;
}
};
/* code provided by PROGIEZ */2940. Find Building Where Alice and Bob Can Meet LeetCode Solution in Java
class Solution {
// Similar to 2736. Maximum Sum Queries
public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
IndexedQuery[] indexedQueries = getIndexedQueries(queries);
int[] ans = new int[queries.length];
Arrays.fill(ans, -1);
// Store indices (heightsIndex) of heights with heights[heightsIndex] in
// descending order.
List<Integer> stack = new ArrayList<>();
// Iterate through queries and heights simultaneously.
int heightsIndex = heights.length - 1;
for (IndexedQuery indexedQuery : indexedQueries) {
final int queryIndex = indexedQuery.queryIndex;
final int a = indexedQuery.a;
final int b = indexedQuery.b;
if (a == b || heights[a] < heights[b]) {
// 1. Alice and Bob are already in the same index (a == b) or
// 2. Alice can jump from a -> b (heights[a] < heights[b]).
ans[queryIndex] = b;
} else {
// Now, a < b and heights[a] >= heights[b].
// Gradually add heights with an index > b to the monotonic stack.
while (heightsIndex > b) {
// heights[heightsIndex] is a better candidate, given that
// heightsIndex is smaller than the indices in the stack and
// heights[heightsIndex] is larger or equal to the heights mapped in
// the stack.
while (!stack.isEmpty() && heights[stack.get(stack.size() - 1)] <= heights[heightsIndex])
stack.remove(stack.size() - 1);
stack.add(heightsIndex--);
}
// Binary search to find the smallest index j such that j > b and
// heights[j] > heights[a], thereby ensuring heights[t] > heights[b].
final int j = lastGreater(stack, a, heights);
if (j != -1)
ans[queryIndex] = stack.get(j);
}
}
return ans;
}
private record IndexedQuery(int queryIndex, int a, int b){};
// Returns the last index i in A s.t. heights[A.get(i)] is > heights[target].
private int lastGreater(List<Integer> A, int target, int[] heights) {
int l = -1;
int r = A.size() - 1;
while (l < r) {
final int m = (l + r + 1) / 2;
if (heights[A.get(m)] > heights[target])
l = m;
else
r = m - 1;
}
return l;
}
private IndexedQuery[] getIndexedQueries(int[][] queries) {
IndexedQuery[] indexedQueries = new IndexedQuery[queries.length];
for (int i = 0; i < queries.length; ++i) {
// Make sure that a <= b.
final int a = Math.min(queries[i][0], queries[i][1]);
final int b = Math.max(queries[i][0], queries[i][1]);
indexedQueries[i] = new IndexedQuery(i, a, b);
}
Arrays.sort(indexedQueries, (a, b) -> Integer.compare(b.b, a.b));
return indexedQueries;
}
}
// code provided by PROGIEZ2940. Find Building Where Alice and Bob Can Meet LeetCode Solution in Python
from dataclasses import dataclass
@dataclass
class IndexedQuery:
queryIndex: int
a: int # Alice's index
b: int # Bob's index
def __iter__(self):
yield self.queryIndex
yield self.a
yield self.b
class Solution:
# Similar to 2736. Maximum Sum Queries
def leftmostBuildingQueries(
self,
heights: list[int],
queries: list[list[int]],
) -> list[int]:
ans = [-1] * len(queries)
# Store indices (heightsIndex) of heights with heights[heightsIndex] in
# descending order.
stack = []
# Iterate through queries and heights simultaneously.
heightsIndex = len(heights) - 1
for queryIndex, a, b in sorted([IndexedQuery(i, min(a, b), max(a, b))
for i, (a, b) in enumerate(queries)],
key=lambda x: -x.b):
if a == b or heights[a] < heights[b]:
# 1. Alice and Bob are already in the same index (a == b) or
# 2. Alice can jump from a -> b (heights[a] < heights[b]).
ans[queryIndex] = b
else:
# Now, a < b and heights[a] >= heights[b].
# Gradually add heights with an index > b to the monotonic stack.
while heightsIndex > b:
# heights[heightsIndex] is a better candidate, given that
# heightsIndex is smaller than the indices in the stack and
# heights[heightsIndex] is larger or equal to the heights mapped in
# the stack.
while stack and heights[stack[-1]] <= heights[heightsIndex]:
stack.pop()
stack.append(heightsIndex)
heightsIndex -= 1
# Binary search to find the smallest index j such that j > b and
# heights[j] > heights[a], thereby ensuring heights[j] > heights[b].
j = self._lastGreater(stack, a, heights)
if j != -1:
ans[queryIndex] = stack[j]
return ans
def _lastGreater(self, A: list[int], target: int, heights: list[int]):
"""
Returns the last index i in A s.t. heights[A.get(i)] is > heights[target].
"""
l = -1
r = len(A) - 1
while l < r:
m = (l + r + 1) // 2
if heights[A[m]] > heights[target]:
l = m
else:
r = m - 1
return l
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.