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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Building Where Alice and Bob Can Meet

Number: 3181

Difficulty: Hard

Paid? No

Companies: Amazon, Infosys

Problem Description

Given an array of building heights and a list of queries where each query provides two starting building indices (for Alice and Bob), determine the leftmost building index where they can meet. A person in building i can move directly to any building j if and only if i < j and heights[i] < heights[j]. Note that a person is already at their starting building, so meeting can occur without any moves. For each query, if such a meeting building exists, return its index (ensuring it is the leftmost possible), otherwise return -1.

Key Insights

  • Each query [a, b] needs to find an index j (with j ≥ max(a, b)) such that: • For the person not already at j, the jump is valid (i < j and heights[i] < heights[j]). • If one of a or b equals j, that person is already there and requires no jump.
  • For two distinct starting indices, let s = min(a, b) and m = max(a, b): • First, check if m itself can be a meeting point by verifying that heights[s] < heights[m] (so that the person at the smaller index can jump to m). • If not, then any valid j must be strictly later than m. In that case the jump condition for both becomes heights[j] > max(heights[a], heights[b]). Thus, we need to find, in the range (m, n), the leftmost index j that satisfies heights[j] > max(heights[a], heights[b]).
  • Since there can be up to 5×10^4 queries and 5×10^4 buildings, linear scanning per query would be too slow. We thus use a segment tree (or a similar data structure) to answer “first index with value > X in a given range” in O(log n) time.

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 the segment tree.

Solution

We first handle the trivial case when both starting positions are the same (return that index). For distinct positions, set s = min(a, b) and m = max(a, b). Check if building m can serve as the meeting building by verifying that the building at s can “jump” to m (i.e. heights[s] < heights[m]). If yes, m is our answer. If not, then both must jump to a later building j > m. In that case, the meeting building must have height greater than both starting heights; that is, heights[j] > max(heights[a], heights[b]). To efficiently find the leftmost such j, we build a segment tree over the heights array. The segment tree is built to allow queries that, given a range and a threshold X, returns the leftmost index in the range where heights[index] > X. Using this structure, answer the query in O(log n) time. Key data structure: • Segment Tree – built to store the maximum height in each segment. To answer a query for the first index with height > X, we first check the maximum in the range; if it is not greater than X, no candidate exists. Otherwise, we descend recursively (preferring the left child) to find the leftmost candidate. This solution uses the fact that a direct jump is allowed and that by choosing the leftmost candidate we satisfy both the movement condition and the problem’s “leftmost meeting building” requirement.

Code Solutions

# Python solution with line-by-line comments

class SegmentTree:
    def __init__(self, heights):
        self.n = len(heights)
        self.heights = heights
        # Tree size up to 4*n is sufficient.
        self.tree = [0] * (4 * self.n)
        self.build(0, 0, self.n - 1)
    
    def build(self, idx, left, right):
        # Build the segment tree storing max value in the segment.
        if left == right:
            self.tree[idx] = self.heights[left]
            return
        mid = (left + right) // 2
        self.build(2 * idx + 1, left, mid)
        self.build(2 * idx + 2, mid + 1, right)
        self.tree[idx] = max(self.tree[2 * idx + 1], self.tree[2 * idx + 2])
    
    def query(self, ql, qr, X, idx, left, right):
        # If current segment is completely outside the query range
        if right < ql or left > qr:
            return -1
        # If maximum in this segment is not greater than X, no candidate exists here.
        if self.tree[idx] <= X:
            return -1
        # If leaf node, return this index since it satisfies condition.
        if left == right:
            return left
        mid = (left + right) // 2
        # Check left child first for the leftmost candidate.
        leftQuery = self.query(ql, qr, X, 2 * idx + 1, left, mid)
        if leftQuery != -1:
            return leftQuery
        # Otherwise, search right child.
        return self.query(ql, qr, X, 2 * idx + 2, mid + 1, right)
    
    def first_index_greater_than(self, start, X):
        return self.query(start, self.n - 1, X, 0, 0, self.n - 1)

def findMeetingBuildings(heights, queries):
    n = len(heights)
    segtree = SegmentTree(heights)
    result = []
    for a, b in queries:
        # If both starting points are same, they already meet.
        if a == b:
            result.append(a)
            continue
        # Set s as the smaller and m as the larger index.
        s, m = min(a, b), max(a, b)
        # Check if the later building m can be the meeting point.
        if heights[s] < heights[m]:
            result.append(m)
        else:
            # Meeting building must have a height greater than both starting buildings.
            threshold = max(heights[a], heights[b])
            # Search for the leftmost index j > m having height > threshold.
            candidate = segtree.first_index_greater_than(m + 1, threshold)
            result.append(candidate if candidate != -1 else -1)
    return result

# Example usage:
# heights = [6,4,8,5,2,7]
# queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
# print(findMeetingBuildings(heights, queries))  # Expected Output: [2,5,-1,5,2]
← Back to All Questions