Find Building Where Alice and Bob Can Meet

Hard

Asked by:

23 views

Topics:

ArraysTwo Pointers

You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the i^th 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 i^th 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 i^th query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.

Example 1:

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: In the first query, Alice and Bob can move to building 2 since heights[0] < heights[2] and heights[1] < heights[2]. 
In the second query, Alice and Bob can move to building 5 since heights[0] < heights[5] and heights[3] < heights[5]. 
In the third query, Alice cannot meet Bob since Alice cannot move to any other building.
In the fourth query, Alice and Bob can move to building 5 since heights[3] < heights[5] and heights[4] < heights[5].
In the fifth query, Alice and Bob are already in the same building.  
For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

Example 2:

Input: heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
Output: [7,6,-1,4,6]
Explanation: In the first query, Alice can directly move to Bob's building since heights[0] < heights[7].
In the second query, Alice and Bob can move to building 6 since heights[3] < heights[6] and heights[5] < heights[6].
In the third query, Alice cannot meet Bob since Bob cannot move to any other building.
In the fourth query, Alice and Bob can move to building 4 since heights[3] < heights[4] and heights[0] < heights[4].
In the fifth query, Alice can directly move to Bob's building since heights[1] < heights[6].
For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

Constraints:

1 <= heights.length <= 5 * 10⁴
1 <= heights[i] <= 10⁹
1 <= queries.length <= 5 * 10⁴
queries[i] = [a_i, b_i]
0 <= a_i, b_i <= heights.length - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `heights` array, and the values of `alice` and `bob`? Are they all non-negative integers?
If there are multiple buildings where Alice and Bob can meet, should I return the one with the smallest index (closest to building 0)?
If Alice or Bob cannot reach any building from their starting point, or if they can reach buildings, but none meet the height requirement, what value should I return?
Is it possible for Alice's or Bob's maximum jump height to be 0?
If `n` (the number of buildings) is 1, should I consider that a valid meeting point if `heights[0]` is less than or equal to both `alice` and `bob`?

Brute Force Solution

Approach

The brute force approach involves trying every possible meeting location for Alice and Bob. We simply go through each building and check if it's a valid meeting point considering their travel constraints. This ensures we don't miss any potential solutions.

Here's how the algorithm would work step-by-step:

Consider the first building as the potential meeting place.
Check if Alice can reach this building within her allowed travel time.
Check if Bob can also reach the same building within his allowed travel time.
If both Alice and Bob can reach the building, then this building is a possible meeting place. Remember this building.
Now, repeat this process for every other building.
After checking all buildings, review the list of possible meeting places. If there are any, then we've found solutions.

Code Implementation

def find_meeting_building(alice_travel_times, bob_travel_times, max_alice_travel_time, max_bob_travel_time):
    possible_meeting_buildings = []
    number_of_buildings = len(alice_travel_times)

    for building_index in range(number_of_buildings):
        # Check if Alice can reach this building within her time
        if alice_travel_times[building_index] <= max_alice_travel_time:

            # Check if Bob can reach this building within his time
            if bob_travel_times[building_index] <= max_bob_travel_time:

                # We need to remember this possible location
                possible_meeting_buildings.append(building_index)

    return possible_meeting_buildings

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n buildings to consider it as a potential meeting point. For each building, it checks if Alice and Bob can reach it within their allowed time. Assuming checking if Alice or Bob can reach a building takes O(n) time (in the worst case, requiring iteration through all other buildings), the total time complexity becomes n * O(n). This simplifies to O(n²), where n is the number of buildings.

Space Complexity

O(1) – The provided approach involves iterating through each building and checking if Alice and Bob can reach it. It remembers possible meeting places. Since the plain English explanation does not describe the use of any data structure whose size is dependent on the input size (number of buildings), the only extra memory used is for a fixed number of variables, such as a variable to store whether a meeting place was found or some index variables. Therefore, the auxiliary space used remains constant regardless of the number of buildings (N). Thus, the space complexity is O(1).

Optimal Solution

Approach

The problem asks us to find a building where both Alice and Bob can see each other. The buildings are arranged in a line, and they can only see each other if there are no taller buildings in between. We can solve this efficiently by checking buildings from both ends of the line towards the middle.

Here's how the algorithm would work step-by-step:

Start by checking the first building for Alice and the last building for Bob.
Keep track of the tallest building Alice can see as she moves from left to right.
Keep track of the tallest building Bob can see as he moves from right to left.
As Alice and Bob move towards each other, compare the height of the current building they're looking at to the tallest they've seen so far. If the current building is taller, update the tallest height.
Keep track of all the buildings that Alice can see (buildings that are taller than any building before them).
Similarly, keep track of all the buildings that Bob can see (buildings that are taller than any building after them).
The building where they can meet must be present in both Alice and Bob's lists of visible buildings. Find the first such building by checking their lists from the outside in.

Code Implementation

def find_meeting_building(building_heights):
    number_of_buildings = len(building_heights)
    alice_visible_buildings = []
    bob_visible_buildings = []
    tallest_alice_can_see = -1
    tallest_bob_can_see = -1

    # Iterate from left to right to find Alice's visible buildings.
    for i in range(number_of_buildings):
        if building_heights[i] > tallest_alice_can_see:
            tallest_alice_can_see = building_heights[i]
            alice_visible_buildings.append(i)

    # Iterate from right to left to find Bob's visible buildings.
    for i in range(number_of_buildings - 1, -1, -1):
        if building_heights[i] > tallest_bob_can_see:
            tallest_bob_can_see = building_heights[i]
            bob_visible_buildings.append(i)

    bob_visible_buildings.reverse()

    # Find the first common building in both lists.
    for alice_building in alice_visible_buildings:
        for bob_building in bob_visible_buildings:
            if alice_building == bob_building:

                #Return the index if they can both see the building.
                return alice_building

    # If no common building is found, return -1.
    return -1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of building heights from both ends towards the middle. One iteration tracks Alice's view, and the other tracks Bob's view, each requiring a single pass through the array. Finding the common visible building also involves iterating through, at most, the buildings each person can see, which is bounded by the total number of buildings. Therefore, the dominant operation is scanning the array a constant number of times related to the size of the array n, giving a time complexity of O(n).

Space Complexity

O(N) – The algorithm uses two lists, one to store buildings Alice can see and another for Bob's visible buildings. In the worst-case scenario, where the buildings are in increasing order from Alice's perspective or decreasing order from Bob's perspective, each list could potentially store all N building indices. Therefore, the auxiliary space required grows linearly with the number of buildings, N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty heights array	Return -1 immediately since no valid building can be found.
Heights array with a single element	Check if the single element's height is within Alice and Bob's jump heights; if so, return 0, otherwise -1.
Alice and Bob cannot reach any buildings (their jump heights are too small)	The solution should return -1 as no building will be marked as reachable by both.
The first and last building are too tall for Alice or Bob respectively	The initial reachable sets for Alice and Bob will be empty, resulting in no meeting point and returning -1.
Only one building satisfies the height constraint for both Alice and Bob	The solution should return the index of that single building if both can reach it.
Large input array leading to potential performance issues	Use an iterative approach with O(n) time complexity to efficiently determine reachable buildings for Alice and Bob.
Integer overflow if heights are very large	Since we are only comparing heights, overflow is not a concern, but language-specific integer limits could be if indexes become too large, handle large index values.
Multiple buildings satisfy the meeting criteria, requiring selection of the closest to building 0	The algorithm should prioritize checking buildings from index 0 onwards, automatically selecting the closest building when it finds a valid meeting point.

Null or empty heights array

How to Handle:

Return -1 immediately since no valid building can be found.

Heights array with a single element

How to Handle:

Check if the single element's height is within Alice and Bob's jump heights; if so, return 0, otherwise -1.

Alice and Bob cannot reach any buildings (their jump heights are too small)

How to Handle:

The solution should return -1 as no building will be marked as reachable by both.

The first and last building are too tall for Alice or Bob respectively

How to Handle:

The initial reachable sets for Alice and Bob will be empty, resulting in no meeting point and returning -1.

Only one building satisfies the height constraint for both Alice and Bob

How to Handle:

The solution should return the index of that single building if both can reach it.

Large input array leading to potential performance issues

How to Handle:

Use an iterative approach with O(n) time complexity to efficiently determine reachable buildings for Alice and Bob.

Integer overflow if heights are very large

How to Handle:

Since we are only comparing heights, overflow is not a concern, but language-specific integer limits could be if indexes become too large, handle large index values.

Multiple buildings satisfy the meeting criteria, requiring selection of the closest to building 0

How to Handle:

The algorithm should prioritize checking buildings from index 0 onwards, automatically selecting the closest building when it finds a valid meeting point.