Find Building Where Alice and Bob Can Meet

• For each query [a, b]:
• Handle the base cases:
  • If a == b, they are at the same building. The answer is a.
  • To simplify, let u = min(a, b) and v = max(a, b).
  • If heights[u] < heights[v], the person at u can move to building v. Since any other meeting place k must be k > v, v is the leftmost possible meeting place. The answer is v.
• If none of the above conditions are met, it means v > u and heights[v] <= heights[u]. They must find a common building k to meet.
• The conditions for a meeting at building k are:
  • k > u and heights[k] > heights[u]
  • k > v and heights[k] > heights[v]
• Combining these, we need to find the smallest k such that k > v and heights[k] > max(heights[u], heights[v]).
• Iterate k from v + 1 to heights.length - 1.
• The first k that satisfies heights[k] > max(heights[u], heights[v]) is the answer.
• If the loop completes without finding such a k, no such meeting place exists, and the answer is -1.

For each query [a, b], we determine the conditions for a meeting. A meeting can happen at a building k if k is to the right of both a and b, and heights[k] is greater than both heights[a] and heights[b]. Let's define v = max(a, b) and h_req = max(heights[a], heights[b]). The problem then becomes finding the smallest index k > v such that heights[k] > h_req.

There are some special conditions to consider first. If a and b are the same, they have already met, so the answer is a. If a and b are different, let's say a < b. If heights[a] < heights[b], Alice can move to Bob's building b. Since any other potential meeting place k must satisfy k > b, b is the leftmost possible option. Thus, the answer is b. A similar logic applies if b < a.

If these special conditions don't apply, we must search for a building k. The brute-force method involves a simple linear scan starting from v + 1 to the end of the heights array, checking the height condition at each step. The first building that satisfies the condition is our answer. If no such building is found after checking all possibilities, it's impossible for them to meet, so we return -1.

1class Solution {2    public int[] canMeet(int[] heights, int[][] queries) {3        int n = heights.length;4        int q = queries.length;5        int[] ans = new int[q];6 7        for (int i = 0; i < q; i++) {8            int u = queries[i][0];9            int v = queries[i][1];10 11            if (u == v) {12                ans[i] = u;13                continue;14            }15 16            if (u > v) {17                int temp = u;18                u = v;19                v = temp;20            }21            // Now u < v22 23            if (heights[u] < heights[v]) {24                ans[i] = v;25                continue;26            }27 28            // Now u < v and heights[u] >= heights[v]29            // Required height is heights[u]30            int requiredHeight = heights[u];31            int meetingPoint = -1;32            for (int k = v + 1; k < n; k++) {33                if (heights[k] > requiredHeight) {34                    meetingPoint = k;35                    break;36                }37            }38            ans[i] = meetingPoint;39        }40        return ans;41    }42}

• Preprocessing Queries:
  • Iterate through each query [a, b] with index q_idx.
  • Handle simple cases first: if a == b, the answer is a. If heights[min(a,b)] < heights[max(a,b)], the answer is max(a,b). Store these answers.
  • For the remaining complex queries, we need to find the smallest k > v = max(a, b) where heights[k] > h = max(heights[a], heights[b]).
  • Group these complex queries by v. A map or an array of lists queriesByV can be used, where queriesByV[v] stores a list of (h, q_idx) pairs.
• Main Loop with Monotonic Stack:
  • Initialize an empty monotonic stack. The stack will store pairs of (height, index).
  • Iterate i from N-1 down to 0.
  • Process Queries: For the current index i, process all queries where v = i. For each such query (h, q_idx):
    • The stack currently contains candidate buildings (h_j, j) where j > i. The stack is maintained such that heights are strictly decreasing from bottom to top.
    • Perform a binary search on the stack to find the candidate (h_j, j) with the smallest index j such that h_j > h. This corresponds to the element at the largest valid index in the stack's underlying array.
    • If a suitable building is found, store its index j as the answer for q_idx. Otherwise, the answer remains -1.
  • Update Stack: After processing queries for v=i, update the stack with the current building i. Pop from the stack while its top element's height is less than or equal to heights[i]. Then, push (heights[i], i) onto the stack. This maintains the monotonic property.

This approach leverages offline processing and a monotonic stack to answer queries efficiently.

First, we categorize the queries. Some can be answered immediately: if a == b, the answer is a. If a < b and heights[a] < heights[b], the answer is b (and vice-versa). The remaining queries require a search. For each such query [a, b], we need to find the smallest k > v = max(a, b) where heights[k] > h = max(heights[a], heights[b]). We group these search queries by their v value into a map, queriesByV.

Next, we iterate backwards from i = heights.length - 1 down to 0. We use a monotonic stack that stores pairs (height, index). This stack maintains a list of candidate buildings, where if (h1, k1) is below (h2, k2) in the stack, then k1 > k2 and h1 > h2.

In each iteration i:

1. We first process all queries that have v = i. For each of these queries, we search the current monotonic stack. The stack contains all optimal candidates with indices greater than i. We can use binary search on the stack's heights to find the best meeting place in O(log N) time.
2. Then, we update the stack with the building at index i. We pop elements from the stack that are shorter or equal in height to heights[i] because i would be a better or equal candidate for any future query. Finally, we push (heights[i], i) onto the stack.

This method processes each building and each query a constant number of times (plus the log N factor for search), leading to a much better time complexity.

1import java.util.*;2 3class Solution {4    public int[] canMeet(int[] heights, int[][] queries) {5        int n = heights.length;6        int q = queries.length;7        int[] ans = new int[q];8        Arrays.fill(ans, -1);9 10        List<int[]>[] queriesByV = new List[n];11        for (int i = 0; i < n; i++) {12            queriesByV[i] = new ArrayList<>();13        }14 15        for (int i = 0; i < q; i++) {16            int u = queries[i][0];17            int v = queries[i][1];18 19            if (u == v) {20                ans[i] = u;21                continue;22            }23            if (heights[u] < heights[v] && u < v) {24                ans[i] = v;25                continue;26            }27            if (heights[v] < heights[u] && v < u) {28                ans[i] = u;29                continue;30            }31 32            int startIdx = Math.max(u, v);33            int requiredHeight = Math.max(heights[u], heights[v]);34            queriesByV[startIdx].add(new int[]{requiredHeight, i});35        }36 37        List<int[]> stack = new ArrayList<>(); // Stores {height, index}38 39        for (int i = n - 1; i >= 0; i--) {40            // Process queries starting after i41            for (int[] query : queriesByV[i]) {42                int requiredHeight = query[0];43                int queryIndex = query[1];44 45                // Binary search on the stack for the first height > requiredHeight46                int low = 0, high = stack.size() - 1;47                int bestIdx = -1;48                while (low <= high) {49                    int mid = low + (high - low) / 2;50                    if (stack.get(mid)[0] > requiredHeight) {51                        bestIdx = stack.get(mid)[1];52                        low = mid + 1; // Try to find a smaller index (further right in stack)53                    } else {54                        high = mid - 1;55                    }56                }57                ans[queryIndex] = bestIdx;58            }59 60            // Update monotonic stack61            while (!stack.isEmpty() && stack.get(stack.size() - 1)[0] <= heights[i]) {62                stack.remove(stack.size() - 1);63            }64            stack.add(new int[]{heights[i], i});65        }66 67        return ans;68    }69}