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].

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] isthe 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.

Examples

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

Solution

Method 1 - Using Priority Queue

The problem requires determining the earliest building (in terms of index) that both Alice and Bob can move to based on their starting positions and the respective heights of the buildings. To solve this efficiently, we leverage a combination of preprocessing, deferred processing, and a priority queue (min-heap):

  1. Immediate Resolution: For some queries, we can immediately decide the result based on the initial heights and positions of Alice and Bob.
  2. Deferred Processing: For queries that cannot be immediately resolved, we store them for later processing when exploring future buildings.
  3. Deferred Query Handling: When processing buildings in order, we use a priority queue to efficiently determine if there are any deferred queries that can now be resolved.

Approach

  1. Preprocessing of Queries:
    • For each query where Alice and Bob start at the same building, they can meet at that building.
    • For queries where Alice’s building height is less than Bob’s and Alice’s index is less than Bob’s, Alice can move directly to Bob’s building.
    • For all other queries, we store the query information to be processed later, deferred to Bob’s index with the height of Alice’s building, marking that the meeting must happen beyond Bob’s starting point.
  2. Processing Deferred Queries:
    • As we iterate through each building:
      • Add deferred queries to a priority queue such that the next possible meeting building is determined based on the smallest height.
      • Check if there are any deferred queries in the priority queue that can be resolved by the current building height.
      • Update the results for queries that can now be resolved, using the current building index as the meeting point.
  3. Cleanup:
    • Ensure all deferred queries remaining in the priority queue are marked as unresolved if they cannot meet the conditions by the end of the array.

Code

Java
class Solution {
    public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
        int n = heights.length, q = queries.length;
        int[] result = new int[q];
        Arrays.fill(result, -1);
        
        // Defer queries initialization
        List<List<int[]>> deferred = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            deferred.add(new ArrayList<>());
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        
        for (int i = 0; i < q; ++i) {
            int a = queries[i][0], b = queries[i][1];
            if (a > b) { int temp = a; a = b; b = temp; }
            if (a == b || heights[a] < heights[b]) {
                result[i] = b;
            } else {
                deferred.get(b).add(new int[]{heights[a], i});
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int[] query : deferred.get(i)) {
                pq.add(query);
            }
            while (!pq.isEmpty() && pq.peek()[0] < heights[i]) {
                result[pq.poll()[1]] = i;
            }
        }

        return result;
    }
}
Python
class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        n = len(heights)
        q = len(queries)
        result = [-1] * q
        
        # Deferred queries initialization
        deferred = [[] for _ in range(n)]
        pq = []

        for i in range(q):
            a, b = queries[i]
            if a > b:
                a, b = b, a
            if a == b or heights[a] < heights[b]:
                result[i] = b
            else:
                deferred[b].append((heights[a], i))

        for i in range(n):
            for query in deferred[i]:
                heapq.heappush(pq, query)
            while pq and pq[0][0] < heights[i]:
                height, index = heapq.heappop(pq)
                result[index] = i

        return result

Complexity

  • ⏰ Time complexity: O(n + q log q), where n is the number of buildings and q is the number of queries.
    • Query Preprocessing: Each query is processed once, resulting in O(q) for q queries.
    • Priority Queue Operations: Each query is added and removed from the queue at most once, resulting in O(q log q) operations, where each insertion and removal takes O(log q) time due to the heap operations.
    • Deferred Query Processing: Each building height is evaluated in the order, leading to O(n) operations for n buildings.
  • 🧺 Space complexity: O(n + q)
    • Deferred Queries Storage: We use an array of lists to store deferred queries, resulting in O(n) space.
    • Result Array: The result array of size q, which is O(q).
    • Priority Queue: At most q elements in the priority queue at any time, leading to O(q) space.