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 * 1041 <= heights[i] <= 1091 <= queries.length <= 5 * 104queries[i] = [ai, bi]0 <= ai, bi <= heights.length - 1This approach involves preprocessing the heights array to identify each building's nearest potential building with greater height. For each query, you can then quickly determine the first such building where both Alice and Bob can move. This significantly reduces unnecessary repeated calculations for multiple queries.
The code first computes the next greater elements for each building using a stack-based approach. The idea is to find the minimum index of the next taller building for each query, where both Alice and Bob can meet. If such a building doesn't exist, the result for that query is -1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + q), where n is the number of buildings and q is the number of queries.
Space Complexity: O(n) for storing the next greater elements.
Another approach is to store a list of building heights and their indices and utilize binary searching techniques to efficiently find the first building both Alice and Bob can move to. This approach prioritizes efficient query handling by using sorted data structures.
The C solution preprocesses the building indexes based on their heights for efficient query handling. It then uses binary search to find potential meeting points for each query.
Time Complexity: O(n log n + q log n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Precompute the Next Greater Element | Time Complexity: O(n + q), where n is the number of buildings and q is the number of queries. |
| Binary Search on Preprocessed Data | Time Complexity: O(n log n + q log n) |
I solved too many Leetcode problems • NeetCodeIO • 101,495 views views
Watch 9 more video solutions →Practice Find Building Where Alice and Bob Can Meet with our built-in code editor and test cases.
Practice on FleetCode