Find Building Where Alice and Bob Can Meet

Hard
1393.

Find Building Where Alice and Bob Can Meet

Find Building Where Alice and Bob Can Meet is a hard coding problem on arrays, binary search and heap, asked in Amazon and Google interviews.

Buildings stand in a row with heights heights[0..n-1]. A person in building i can move to building j only if i < j and heights[i] < heights[j]; staying put is always allowed.

Each query queries[t] = [a, b] places Alice in building a and Bob in building b. Find the leftmost building where both of them can be — each reaching it in at most one move from their start.

Return an array whose t-th entry is that building's index, or -1 if no building works.

Example 1

Input
heights = [3,1,4,1,5], queries = [[0,1],[1,2],[3,3],[2,0],[4,2]]
Output
[2,2,3,2,4]
Explanation
For [0,1] both can move to building 2 (height 4); for [2,0] Alice is already where Bob can climb to.

Example 2

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
For [2,4] nothing to the right of building 4 is taller than 8.

Constraints

  • 1 <= heights.length <= 5 * 10^4
  • 1 <= heights[i] <= 10^9
  • 1 <= queries.length <= 5 * 10^4
  • queries[t] = [a, b]
  • 0 <= a, b <= heights.length - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} heights
 * @param {number[][]} queries
 * @return {number[]}
 */
var leftmostBuildingQueries = function(heights, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Building Where Alice and Bob Can Meet — Solution

Find Building Where Alice and Bob Can Meet solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Find Building Where Alice and Bob Can Meet is a hard coding problem on arrays, binary search and heap, asked in Amazon and Google interviews.

Problem statement

Buildings stand in a row with heights heights[0..n-1]. A person in building i can move to building j only if i < j and heights[i] < heights[j]; staying put is always allowed.

Each query queries[t] = [a, b] places Alice in building a and Bob in building b. Find the leftmost building where both of them can be — each reaching it in at most one move from their start.

Return an array whose t-th entry is that building's index, or -1 if no building works.

Example 1

Input: heights = [3,1,4,1,5], queries = [[0,1],[1,2],[3,3],[2,0],[4,2]]
Output: [2,2,3,2,4]
Explanation: For [0,1] both can move to building 2 (height 4); for [2,0] Alice is already where Bob can climb to.

Example 2

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: For [2,4] nothing to the right of building 4 is taller than 8.

Constraints

  • 1 <= heights.length <= 5 * 10^4
  • 1 <= heights[i] <= 10^9
  • 1 <= queries.length <= 5 * 10^4
  • queries[t] = [a, b]
  • 0 <= a, b <= heights.length - 1

Hints for Find Building Where Alice and Bob Can Meet

  1. Hint 1

    Order each query so that a <= b. If a == b, or the person on the left is shorter than the building on the right, the answer is simply b.

  2. Hint 2

    Otherwise both must move to some j > b taller than heights[a] (which is at least heights[b]) — the answer is the leftmost such j.

  3. Hint 3

    Answer those queries offline from right to left: keep a monotonic stack of indices to the right of b whose heights are prefix maxima, and binary-search it for the nearest one taller than heights[a].

How to solve Find Building Where Alice and Bob Can Meet

After sorting each pair so a < b, the hard case asks for the leftmost index after b whose height exceeds heights[a]. Sweeping from the right while maintaining a monotonic stack makes those candidates sorted by both index and height, so each query is one binary search.

Approach

  1. For each query, let a = min, b = max. If a == b or heights[a] < heights[b], the answer is b. Otherwise file the query under index b with threshold v = heights[a].
  2. Walk i from n - 1 down to 0. First answer the queries filed under i, then push i after popping every stack index whose height is <= heights[i].
  3. The stack (bottom to top) holds indices with strictly decreasing heights and decreasing positions; the leftmost index taller than v is the topmost entry whose height is > v. Binary-search the boundary; if no entry is taller, the answer is -1.

Why it works

When queries at i are answered, the stack holds exactly the indices j > i that are taller than everything between i + 1 and j - 1 — the running maxima seen from i. The first index after i that exceeds v is necessarily one of these running maxima, and because heights fall towards the top of the stack, the entries taller than v form a contiguous block at the bottom whose last element is the leftmost such index.

Complexity

  • Time — O((n + q) log n)
  • Space — O(n + q)

Pitfalls

  • Normalise every query to a <= b first — queries may list Bob before Alice.
  • Equal heights do not allow a move: the target must be strictly taller than both.
  • When heights[a] < heights[b], building b itself is the answer; no search is needed.

Reference solution

Python

from typing import List

def leftmostBuildingQueries(heights: List[int], queries: List[List[int]]) -> List[int]:
    n = len(heights)
    res = [-1] * len(queries)
    pending = [[] for _ in range(n)]
    for qi, (x, y) in enumerate(queries):
        a, b = min(x, y), max(x, y)
        if a == b or heights[a] < heights[b]:
            res[qi] = b
        else:
            pending[b].append((heights[a], qi))
    st = []
    for i in range(n - 1, -1, -1):
        for v, qi in pending[i]:
            lo, hi = 0, len(st)
            while lo < hi:
                mid = (lo + hi) // 2
                if heights[st[mid]] > v:
                    lo = mid + 1
                else:
                    hi = mid
            res[qi] = st[lo - 1] if lo > 0 else -1
        while st and heights[st[-1]] <= heights[i]:
            st.pop()
        st.append(i)
    return res

Java

public static int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
    int n = heights.length, qn = queries.length;
    int[] res = new int[qn];
    Arrays.fill(res, -1);
    List<List<Integer>> pending = new ArrayList<>();
    for (int i = 0; i < n; i++) pending.add(new ArrayList<>());
    for (int q = 0; q < qn; q++) {
        int a = Math.min(queries[q][0], queries[q][1]);
        int b = Math.max(queries[q][0], queries[q][1]);
        if (a == b || heights[a] < heights[b]) res[q] = b;
        else pending.get(b).add(q);
    }
    int[] st = new int[n];
    int top = 0;
    for (int j = n - 1; j >= 0; j--) {
        for (int qi : pending.get(j)) {
            int v = heights[Math.min(queries[qi][0], queries[qi][1])];
            int lo = 0, hi = top;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (heights[st[mid]] > v) lo = mid + 1; else hi = mid;
            }
            res[qi] = lo > 0 ? st[lo - 1] : -1;
        }
        while (top > 0 && heights[st[top - 1]] <= heights[j]) top--;
        st[top++] = j;
    }
    return res;
}

C++

vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
    int n = heights.size(), qn = queries.size();
    vector<int> res(qn, -1);
    vector<vector<int>> pending(n);
    for (int q = 0; q < qn; q++) {
        int a = min(queries[q][0], queries[q][1]);
        int b = max(queries[q][0], queries[q][1]);
        if (a == b || heights[a] < heights[b]) res[q] = b;
        else pending[b].push_back(q);
    }
    vector<int> st;
    for (int j = n - 1; j >= 0; j--) {
        for (int qi : pending[j]) {
            int v = heights[min(queries[qi][0], queries[qi][1])];
            int lo = 0, hi = st.size();
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (heights[st[mid]] > v) lo = mid + 1; else hi = mid;
            }
            res[qi] = lo > 0 ? st[lo - 1] : -1;
        }
        while (!st.empty() && heights[st.back()] <= heights[j]) st.pop_back();
        st.push_back(j);
    }
    return res;
}

JavaScript

var leftmostBuildingQueries = function(heights, queries) {
    var n = heights.length;
    var res = new Array(queries.length).fill(-1);
    var pending = [];
    for (var i = 0; i < n; i++) pending.push([]);
    for (var q = 0; q < queries.length; q++) {
        var a = Math.min(queries[q][0], queries[q][1]);
        var b = Math.max(queries[q][0], queries[q][1]);
        if (a === b || heights[a] < heights[b]) res[q] = b;
        else pending[b].push(q);
    }
    var st = [];
    for (var j = n - 1; j >= 0; j--) {
        var list = pending[j];
        for (var t = 0; t < list.length; t++) {
            var qi = list[t];
            var v = heights[Math.min(queries[qi][0], queries[qi][1])];
            var lo = 0, hi = st.length;
            while (lo < hi) {
                var mid = (lo + hi) >> 1;
                if (heights[st[mid]] > v) lo = mid + 1; else hi = mid;
            }
            res[qi] = lo > 0 ? st[lo - 1] : -1;
        }
        while (st.length > 0 && heights[st[st.length - 1]] <= heights[j]) st.pop();
        st.push(j);
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search