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

Approach 01:

#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

struct IndexedQuery {
    int queryIndex;
    int aliceIndex; // Alice's index
    int bobIndex;   // Bob's index

    IndexedQuery(int qIndex, int a, int b)
        : queryIndex(qIndex), aliceIndex(a), bobIndex(b) {}

    bool operator<(const IndexedQuery &other) const {
        return bobIndex > other.bobIndex;
    }
};

class Solution {
public:
    vector<int> leftmostBuildingQueries(vector<int> &buildingHeights, vector<vector<int>> &queries) {
        vector<int> results(queries.size(), -1);
        vector<int> monotonicStack;

        int buildingIndex = buildingHeights.size() - 1;
        vector<IndexedQuery> sortedQueries;
        for (int i = 0; i < queries.size(); ++i) {
            int aliceIndex = min(queries[i][0], queries[i][1]);
            int bobIndex = max(queries[i][0], queries[i][1]);
            sortedQueries.emplace_back(i, aliceIndex, bobIndex);
        }

        sort(sortedQueries.begin(), sortedQueries.end());

        for (const auto &query : sortedQueries) {
            int queryIndex = query.queryIndex;
            int aliceIndex = query.aliceIndex;
            int bobIndex = query.bobIndex;

            if (aliceIndex == bobIndex || buildingHeights[aliceIndex] < buildingHeights[bobIndex]) {
                results[queryIndex] = bobIndex;
            } else {
                while (buildingIndex > bobIndex) {
                    while (!monotonicStack.empty() && buildingHeights[monotonicStack.back()] <= buildingHeights[buildingIndex]) {
                        monotonicStack.pop_back();
                    }
                    monotonicStack.push_back(buildingIndex);
                    --buildingIndex;
                }

                int lastGreaterIndex = lastGreater(monotonicStack, aliceIndex, buildingHeights);
                if (lastGreaterIndex != -1) {
                    results[queryIndex] = monotonicStack[lastGreaterIndex];
                }
            }
        }

        return results;
    }

private:
    int lastGreater(const vector<int> &indexList, int targetIndex, const vector<int> &buildingHeights) {
        int left = -1, right = indexList.size() - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (buildingHeights[indexList[mid]] > buildingHeights[targetIndex]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

from dataclasses import dataclass


@dataclass
class IndexedQuery:
    queryIndex: int
    aliceIndex: int  # Alice's index
    bobIndex: int  # Bob's index

    def __iter__(self):
        yield self.queryIndex
        yield self.aliceIndex
        yield self.bobIndex


class Solution:
    def leftmostBuildingQueries(self, buildingHeights: list[int], queries: list[list[int]]) -> list[int]:
        results = [-1] * len(queries)
        monotonicStack = []

        buildingIndex = len(buildingHeights) - 1
        for queryIndex, aliceIndex, bobIndex in sorted(
            [IndexedQuery(i, min(a, b), max(a, b)) for i, (a, b) in enumerate(queries)],
            key=lambda x: -x.bobIndex
        ):
            if aliceIndex == bobIndex or buildingHeights[aliceIndex] < buildingHeights[bobIndex]:
                results[queryIndex] = bobIndex
            else:
                while buildingIndex > bobIndex:
                    while monotonicStack and buildingHeights[monotonicStack[-1]] <= buildingHeights[buildingIndex]:
                        monotonicStack.pop()
                    monotonicStack.append(buildingIndex)
                    buildingIndex -= 1

                lastGreaterIndex = self._lastGreater(monotonicStack, aliceIndex, buildingHeights)
                if lastGreaterIndex != -1:
                    results[queryIndex] = monotonicStack[lastGreaterIndex]

        return results

    def _lastGreater(self, indexList: list[int], targetIndex: int, buildingHeights: list[int]):
        left = -1
        right = len(indexList) - 1
        while left < right:
            mid = (left + right + 1) // 2
            if buildingHeights[indexList[mid]] > buildingHeights[targetIndex]:
                left = mid
            else:
                right = mid - 1
        return left

Time Complexity

• Sorting Queries:
  • The queries are sorted based on bobIndex, requiring \( O(q \log q) \), where \( q \) is the number of queries.
• Building Processing:
  • The outer loop processes each query, iterating through the sorted queries, which is \( O(q) \).
  • The inner loop iterates through building heights starting from the end and maintains a monotonic stack, which processes each building at most once, resulting in \( O(n) \), where \( n \) is the number of buildings.
• Binary Search for Last Greater Index:
  • The binary search for the last greater index in the monotonic stack is \( O(\log n) \) per query.
  • For \( q \) queries, this becomes \( O(q \log n) \).
• Overall Time Complexity:

  The total time complexity is: \( O(q \log q + n + q \log n) \)

Space Complexity

• Input Storage:
  • The input vectors buildingHeights and queries require \( O(n + q) \) space.
• Auxiliary Storage:
  • The monotonic stack stores building indices, requiring \( O(n) \) space in the worst case.
  • The sorted queries list stores \( q \) elements, requiring \( O(q) \) space.
• Overall Space Complexity:

  The total space complexity is: \( O(n + q) \)