Find building where alice and bob can meet

Array Binary Search Stack Binary Indexed Tree Segment Tree Heap (Priority Queue) Monotonic Stack

52.2% acceptance

Feb 25, 2026

842

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn leftmost_building_queries(heights: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    let n = heights.len();
    let q = queries.len();
    let mut ans = vec![-1i32; q];

    // For each query, normalize so a <= b
    // Case 1: a == b -> answer is a
    // Case 2: heights[a] < heights[b] -> answer is b
    // Case 3: otherwise need smallest c > b with heights[c] > max(heights[a], heights[b])
    //   required height > max(heights[a], heights[b])

    // pending[i] = [(required_height, query_index)] for queries that need first building > i with height > required
    let mut pending: Vec<Vec<(i32, usize)>> = vec![vec![]; n];

    for (qi, query) in queries.iter().enumerate() {
      let mut a = query[0] as usize;
      let mut b = query[1] as usize;
      if a > b {
        std::mem::swap(&mut a, &mut b);
      }
      if a == b {
        ans[qi] = a as i32;
      } else if heights[a] < heights[b] {
        ans[qi] = b as i32;
      } else {
        // Need first c > b with heights[c] > heights[a] (since heights[a] >= heights[b])
        let req = heights[a];
        pending[b].push((req, qi));
      }
    }

    // Sweep from left to right, maintain min-heap of (required_height, query_index)
    let mut heap: BinaryHeap<Reverse<(i32, usize)>> = BinaryHeap::new();

    for i in 0..n {
      // Process pending queries that start at building i (need c > i)
      // Actually we process queries attached to b, and look for c > b
      // So when we reach building i, we add queries with b = i-1? No.
      // We attach pending queries at index b; when we process index i > b, we resolve them.
      // So we first check if current building resolves pending queries, then add new pending.

      // Resolve queries where heights[i] > required height
      while let Some(&Reverse((req, qi))) = heap.peek() {
        if heights[i] > req {
          heap.pop();
          ans[qi] = i as i32;
        } else {
          break;
        }
      }

      // Add new pending queries for b = i
      for &(req, qi) in &pending[i] {
        heap.push(Reverse((req, qi)));
      }
    }

    ans
  }
}