Skip to content

2940. Find Building Where Alice and Bob Can Meet 👍

  • Time: $O(\texttt{sort}(q) + (q + n)\log n)$
  • Space: $O(n + q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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