We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Building Where Alice and Bob Can Meet

Difficulty: Hard

Problem Description

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] = [a_i, b_i]. On the ith query, Alice is in building a_i while Bob is in building b_i. 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.

Key Insights

  • Alice and Bob can only move to buildings that are to the right and have greater heights than their current buildings.
  • We need to find the leftmost building that both can reach based on their starting positions.
  • The problem can be efficiently solved using a monotonic stack to keep track of reachable buildings.

Space and Time Complexity

Time Complexity: O(n + q * log(n)), where n is the number of buildings and q is the number of queries.
Space Complexity: O(n), for storing the results of the reachable buildings.

Solution

To solve this problem, we can use a combination of a monotonic stack and binary search. The idea is to preprocess the heights array to create an array next_higher that stores the next building index with a height greater than the current building. This allows us to quickly determine which buildings Alice and Bob can access. For each query, we can then perform a binary search on the potential meeting buildings to find the leftmost one they can reach.

  1. Create an array next_higher initialized to -1, which will store the index of the next taller building for each building.
  2. Use a monotonic stack to fill in the next_higher values by iterating through the heights array from right to left.
  3. For each query, use the starting positions of Alice and Bob to find the first accessible building using the next_higher array and return the leftmost index that both can reach.

Code Solutions

def find_building(heights, queries):
    n = len(heights)
    next_higher = [-1] * n
    stack = []

    # Fill next_higher using a monotonic stack
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] <= heights[i]:
            stack.pop()
        if stack:
            next_higher[i] = stack[-1]
        stack.append(i)

    results = []
    for a, b in queries:
        meet_index = -1
        # Check from Alice's position
        current = a
        while current != -1 and current < n:
            if current > b:
                break
            meet_index = max(meet_index, current)
            current = next_higher[current]
        
        current = b
        while current != -1 and current < n:
            if current > a:
                break
            meet_index = max(meet_index, current)
            current = next_higher[current]

        results.append(meet_index)

    return results
← Back to All Questions