2940. Find Building Where Alice and Bob Can Meet


Problem Description

In this problem, we have an array of positive integers named heights that represent the heights of buildings, indexed starting at 0. Individuals can move from one building to another if the building they are moving to has a greater height and a higher index. Practically, one can only move to taller buildings on their right.

Additionally, we are given several pairs of buildings in the queries array. Each pair [a_i, b_i] represents buildings where Alice starts at a_i and Bob starts at b_i. The goal is to determine the first building to the right of both starting buildings where Alice and Bob can meet, obeying the movement rule. We should return an array with the leftmost such meeting building for each query, or -1 if such a meeting building does not exist for a certain query.

Intuition

For this particular problem, the intuitive first step might be to consider a brute-force approach, where for every query, we try to step through each building between Alice and Bob until we find a common meeting point if one exists. However, this approach becomes inefficient for large arrays, and hence we need a better strategy.

One key realization is that if Alice is already at a building equal or taller than Bob's building, then the answer is straightforward - the meeting point is Bob's building. Otherwise, we require a strategy to efficiently find the leftmost taller building where they can meet.

To optimize this process, we can use a Binary Indexed Tree (BIT) to quickly query the minimum index of a building with a specific height. Moreover, we process the queries in order of descending r_i (the higher-indexed building in the pair) using a pointer j to keep track of which buildings we've added to the BIT. This allows us to only consider buildings once and to use our BIT to quickly find the leftmost building tall enough for Alice if necessary.

Binary Indexed Tree Explained

A Binary Indexed Tree or a Fenwick Tree is a data structure that provides efficient methods for cumulative frequency tables. It supports updating an element and querying prefix sums in logarithmic time, which in our case is used to quickly identify the leftmost building where Alice and Bob could meet.

When we get a query, we check if Alice can meet Bob at Bob's current building. If not, we update our BIT with buildings that have not yet been considered and then use the tree to find the smallest index of a building taller than Alice's current building.

The process requires discretization of height values, which simply means to map the heights to an array index to use them in the BIT.

The time complexity of this approach is O((n + m) * log n + m * log m), where n is the number of buildings and m is the number of queries. This is due to sorting the queries and heights, and operations in BIT, which are logarithmic with respect to the number of buildings.

The binary indexed tree substantially optimizes the process by allowing for efficient minimum index queries, thus making it feasible to efficiently solve problems of this type, which would otherwise require a brute force approach.

Learn more about Stack, Segment Tree, Binary Search, Monotonic Stack and Heap (Priority Queue) patterns.

Solution Approach

The solution leverages a Binary Indexed Tree (BIT) to efficiently locate the leftmost building where Alice and Bob can meet for each query. Here's a detailed explanation of the implementation:

  • Discretization of Heights: Since heights could be large and sparsely distributed, we first discretize them, which involves mapping each unique height to a unique integer in a smaller consecutive range. This allows us to use these new integer mappings as indices in our BIT.

  • Sorting Queries by r_i: We sort the queries in descending order of r_i (second value of each pair) so we can process them from right to left. This ordering allows us to maintain a BIT according to the buildings we have already checked.

  • Binary Indexed Tree (Fenwick Tree) Usage:

    • The BIT we implement is a slight variation — instead of summing values, we're maintaining the minimum index encountered for a given height.
    • The BIT has two main operations: update and query.
      • update: This takes a height (after discretization) and an index and updates the BIT to mark the minimum index for that height. Given the nature of the problem, if a height has already been encountered at a lower index, we don't need to update it again since we're only interested in the leftmost building.
      • query: This retrieves the minimum index for buildings taller than a certain height, employing a cumulative minimum operation.
  • Processing Each Query:

    • We iterate over each query, and add buildings to the BIT if their index j is greater than the current query's higher index r. This is done in a loop where we decrease j and update our tree every time.
    • For every query [l, r], we check two cases:
      1. If l == r or heights[l] < heights[r]: Bob is reachable by Alice directly, so the meeting building's index r becomes the answer.
      2. Else, we must look for taller buildings to Alice's right. We query our BIT for the minimum index of buildings taller than the one Alice is currently in.
    • The answer from the BIT is then the answer to our query. If there are no such buildings (returned value is inf), then we record -1.
  • Time Complexity:

    • Sorting the queries: O(m * log m) where m is the number of queries.
    • Sorting for discretization: O(n * log n) where n is the number of buildings.
    • Processing queries and updating/querying the BIT: O((n + m) * log n).

By using a BIT, we efficiently reduce the time complexity of checking potential meeting buildings from linear time (O(n)) in a brute-force approach down to logarithmic time (O(log n)). This significant optimization allows us to handle large-scale problems that would otherwise be computationally impractical.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. We'll be using an array of heights and a set of queries to demonstrate how the Binary Indexed Tree (BIT) can help find meeting points efficiently.

Heights Array: [3, 1, 4, 2, 5]

Queries Array: [[1, 2], [0, 4], [3, 4]]

Each building's index corresponds to its position in the array, and the value is its height. We want to find the first building to the right of both Alice's (a_i) and Bob's (b_i) starting buildings that they can meet at.

First, we'll discretize the heights to [2, 1, 3, 2, 4], as there are four unique heights.

Next, we sort the queries by the second value (r_i) in descending order: [[0, 4], [3, 4], [1, 2]].

Now, let's process each query using the BIT:

  1. Query [0, 4]:

    • Alice starts at building 0 with height 3, and Bob starts at building 4 with height 5.
    • Since Alice's building is shorter, we check for buildings taller than height 3 to the right. We update the BIT with buildings up to index 4.
    • The BIT now contains the following minimum indices for the given heights: height 2 -> index 1, height 3 -> index 2, height 5 -> index 4
    • We find that the first building taller than height 3 (Alice's height) from the BIT is at index 4, which matches Bob's starting point.
    • The result for this query is index 4.
  2. Query [3, 4]:

    • Alice moves from building 3 with height 2, and Bob starts again at building 4 with height 5.
    • Since Alice's building is shorter, we look for taller buildings again.
    • No need to update the BIT further as all buildings have been considered.
    • The first building taller than height 2 (Alice's height) is at index 2.
    • In this case, however, index 2 is to the left of Bob's starting index (index 4), so it does not count as a meeting point.
    • We continue searching and find that the next tallest building is at index 4, which is where Bob is.
    • The result for this query is index 4.
  3. Query [1, 2]:

    • Alice starts at building 1 with height 1, and Bob is at building 2 with height 4.
    • Alice can directly meet Bob at building 2 as it's greater in height, so we need not query the BIT.
    • The result for this query is index 2.

After processing all queries using our BIT for minimum index lookup, the results array will be [4, 4, 2]. This corresponds to the first building to the right of both Alice's and Bob's starting buildings where they can meet, for each of their respective queries. If a meeting point doesn't exist, we would return -1 for that query.

The described process leverages the efficiency of the BIT to quickly identify potential meeting buildings, optimizing the overall time complexity of the solution.

Solution Implementation

1from typing import List
2from bisect import bisect_left
3from math import inf
4
5class BinaryIndexedTree:
6    def __init__(self, size: int):
7        self.size = size  # represents the number of elements
8        self.tree_array = [inf] * (size + 1)  # The tree array is initialized with 'inf'
9
10    def update(self, index: int, value: int):
11        # Update the tree with the new value at the given index
12        while index <= self.size:
13            self.tree_array[index] = min(self.tree_array[index], value)
14            index += index & -index  # Move to the next index to update
15
16    def query(self, index: int) -> int:
17        # Retrieve the minimum value up to the given index
18        min_value = inf
19        while index:
20            min_value = min(min_value, self.tree_array[index])
21            index -= index & -index  # Move to the parent index
22        return -1 if min_value == inf else min_value
23
24
25class Solution:
26    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
27        num_buildings, num_queries = len(heights), len(queries)
28        # Normalize queries such that each query is [min, max]
29        for i in range(num_queries):
30            queries[i] = [min(queries[i]), max(queries[i])]
31
32        # Reverse sort the building indices by their rightmost building of the range
33        sorted_queries_indices = sorted(range(num_queries), key=lambda i: -queries[i][1])
34      
35        answers = [-1] * num_queries  # Initialize default answers to -1
36        binary_indexed_tree = BinaryIndexedTree(num_buildings)
37
38        # Sort unique heights for later binary search use
39        unique_sorted_heights = sorted(set(heights))
40        last_processed_building = num_buildings - 1  # Keeps track of last building processed in the BIT
41
42        # Check queries in descending order of right boundary
43        for query_index in sorted_queries_indices:
44            left_bound, right_bound = queries[query_index]
45            # Ensure that all relevant heights have been processed in the BIT
46            while last_processed_building > right_bound:
47                height_index = num_buildings - bisect_left(unique_sorted_heights, heights[last_processed_building]) + 1
48                binary_indexed_tree.update(height_index, last_processed_building)
49                last_processed_building -= 1
50
51            # If left and right are the same, or left building is shorter than right, answer is trivial
52            if left_bound == right_bound or heights[left_bound] < heights[right_bound]:
53                answers[query_index] = right_bound
54            else:
55                # Find the leftmost building that is not shorter than the one at left_bound
56                height_index = num_buildings - bisect_left(unique_sorted_heights, heights[left_bound])
57                answers[query_index] = binary_indexed_tree.query(height_index)
58
59        return answers
60
1import java.util.Arrays;
2
3// BinaryIndexedTree class for range queries and updates
4class BinaryIndexedTree {
5    // A large number representing `infinity`
6    private static final int INFINITY = 1 << 30;
7    // The size of the tree
8    private int size;
9    // Internal storage of the Binary Indexed Tree
10    private int[] tree;
11
12    // BinaryIndexedTree constructor
13    public BinaryIndexedTree(int size) {
14        this.size = size;
15        // Initialize the internal storage with 'infinity' values
16        tree = new int[size + 1];
17        Arrays.fill(tree, INFINITY);
18    }
19
20    // Update the tree with value 'v' at the index 'x'
21    public void update(int x, int v) {
22        while (x <= size) {
23            tree[x] = Math.min(tree[x], v);
24            // Move to the next index to update
25            x += x & -x;
26        }
27    }
28
29    // Query the tree for the minimum value until index 'x'
30    public int query(int x) {
31        int minimum = INFINITY;
32        while (x > 0) {
33            minimum = Math.min(minimum, tree[x]);
34            // Move to the previous index to query
35            x -= x & -x;
36        }
37        // If the minimum is INFINITY, return -1, as it implies no update was made
38        return minimum == INFINITY ? -1 : minimum;
39    }
40}
41
42class Solution {
43    // Process leftmost building queries
44    public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
45        int buildingsLength = heights.length;
46        int queriesLength = queries.length;
47      
48        // Ensure the start of the range is less than the end of the range
49        for (int i = 0; i < queriesLength; ++i) {
50            if (queries[i][0] > queries[i][1]) {
51                queries[i] = new int[] {queries[i][1], queries[i][0]};
52            }
53        }
54      
55        // Array of query indices for sorting
56        Integer[] indices = new Integer[queriesLength];
57        for (int i = 0; i < queriesLength; ++i) {
58            indices[i] = i;
59        }
60      
61        // Sort query indices based on the right bound of queries in descending order
62        Arrays.sort(indices, (i, j) -> queries[j][1] - queries[i][1]);
63      
64        // Copy and sort building heights
65        int[] sortedHeights = heights.clone();
66        Arrays.sort(sortedHeights);
67      
68        // Initialize result array
69        int[] results = new int[queriesLength];
70      
71        // Initialize Binary Indexed Tree
72        BinaryIndexedTree tree = new BinaryIndexedTree(buildingsLength);
73      
74        // Iterator from right to left on buildings
75        int j = buildingsLength - 1;
76      
77        // Process queries based on sorted indices
78        for (int index : indices) {
79            int leftBound = queries[index][0], rightBound = queries[index][1];
80            // Updating tree
81            while (j > rightBound) {
82                // Find position in sorted array for the height of building 'j'
83                int position = buildingsLength - Arrays.binarySearch(sortedHeights, heights[j]) + 1;
84                // Update the tree at position with building index 'j'
85                tree.update(position, j);
86                --j;
87            }
88            // Check for direct visibility or use the Binary Indexed Tree to find leftmost building
89            if (leftBound == rightBound || heights[leftBound] < heights[rightBound]) {
90                results[index] = rightBound;
91            } else {
92                int k = buildingsLength - Arrays.binarySearch(sortedHeights, heights[leftBound]);
93                results[index] = tree.query(k);
94            }
95        }
96        return results;
97    }
98}
99
1#include <vector>
2#include <algorithm>
3#include <numeric>
4
5using namespace std;
6
7class BinaryIndexedTree {
8private:
9    const int INFINITY = 1 << 30; // Setting a high value to simulate infinity.
10    int size_;
11    vector<int> treeArray_;
12
13public:
14    // Constructor that initializes the binary indexed tree.
15    BinaryIndexedTree(int size) {
16        this->size_ = size;
17        treeArray_.resize(size + 1, INFINITY);
18    }
19  
20    // Updates the binary indexed tree with a value at position x.
21    void update(int x, int value) {
22        while (x <= size_) {
23            treeArray_[x] = min(treeArray_[x], value);
24            x += x & -x; // Move x to the next index to be updated.
25        }
26    }
27  
28    // Queries the minimum value until index x.
29    int query(int x) {
30        int minimumValue = INFINITY;
31        while (x > 0) {
32            minimumValue = min(minimumValue, treeArray_[x]);
33            x -= x & -x; // Move x to the parent index.
34        }
35        return minimumValue == INFINITY ? -1 : minimumValue; // If no update was made, return -1.
36    }
37};
38
39class Solution {
40public:
41    vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
42        int heightSize = heights.size();
43        int queriesSize = queries.size();
44      
45        // Standardize queries to ensure left index is less than right index.
46        for (auto& query : queries) {
47            if (query[0] > query[1]) {
48                swap(query[0], query[1]);
49            }
50        }
51      
52        // Indexes to track original order of queries after sorting.
53        vector<int> queryIndexes(queriesSize);
54        iota(queryIndexes.begin(), queryIndexes.end(), 0);
55      
56        // Sort the indexes based on the right boundaries of queries in descending order.
57        sort(queryIndexes.begin(), queryIndexes.end(), [&](int i, int j) {
58            return queries[j][1] < queries[i][1];
59        });
60      
61        // Sort the heights and remove duplicates.
62        vector<int> sortedHeights = heights;
63        sort(sortedHeights.begin(), sortedHeights.end());
64        sortedHeights.erase(unique(sortedHeights.begin(), sortedHeights.end()), sortedHeights.end());
65      
66        vector<int> answers(queriesSize);
67        int j = heightSize - 1;
68        BinaryIndexedTree tree(heightSize);
69      
70        // Iterate through queries in the order of their sorted right boundaries.
71        for (int queryIndex : queryIndexes) {
72            int left = queries[queryIndex][0], right = queries[queryIndex][1];
73            while (j > right) {
74                int k = lower_bound(sortedHeights.begin(), sortedHeights.end(), heights[j]) - sortedHeights.begin() + 1;
75                tree.update(k, j);
76                --j;
77            }
78            if (left == right || heights[left] < heights[right]) {
79                answers[queryIndex] = right;
80            } else {
81                int k = lower_bound(sortedHeights.begin(), sortedHeights.end(), heights[left]) - sortedHeights.begin();
82                answers[queryIndex] = tree.query(k);
83            }
84        }
85      
86        return answers;
87    }
88};
89
1let n: number; // Store the number of buildings
2let bitArray: number[]; // Represents the Binary Indexed Tree (BIT) array
3const INF: number = 1 << 30; // Setting an infinity value for comparisons
4
5// Initialize global variables for the number of buildings and the BIT array
6function initialize(nVal: number): void {
7    n = nVal;
8    bitArray = Array(n + 1).fill(INF);
9}
10
11// Updating the BIT array with a new value, considering the minimum
12function update(x: number, value: number): void {
13    while (x <= n) {
14        bitArray[x] = Math.min(bitArray[x], value);
15        x += x & -x; // Traverse to parent node in BIT
16    }
17}
18
19// Querying the minimum value within a range [1, x] in the BIT
20function query(x: number): number {
21    let minValue = INF;
22    while (x > 0) {
23        minValue = Math.min(minValue, bitArray[x]);
24        x -= x & -x; // Traverse to the next node to process
25    }
26    return minValue === INF ? -1 : minValue;
27}
28
29// Process all the queries to find the leftmost building that can be seen
30function leftmostBuildingQueries(heights: number[], queries: number[][]): number[] {
31    const numBuildings = heights.length;
32    const numQueries = queries.length;
33
34    // Sorting queries based on the right boundary in decreasing order
35    const sortedQueryIndices: number[] = [...Array(numQueries).keys()];
36    sortedQueryIndices.sort((i, j) => queries[j][1] - queries[i][1]);
37
38    const results: number[] = Array(numQueries).fill(-1); // Storing the results of the queries
39    const sortedHeights = [...heights].sort((a, b) => a - b); // Sort building heights for binary searching
40
41    // Binary search to find the position of the given height in the sorted heights array
42    function heightPosition(height: number): number {
43        let left = 0, right = numBuildings;
44        while (left < right) {
45            const mid = (left + right) >> 1;
46            if (sortedHeights[mid] >= height) {
47                right = mid;
48            } else {
49                left = mid + 1;
50            }
51        }
52        return left;
53    }
54
55    // Processing each query based on their sorted order
56    let rightmostIndex = numBuildings - 1;
57    for (const queryIndex of sortedQueryIndices) {
58        const [left, right] = queries[queryIndex];
59
60        // Updating the BIT with the indices of buildings from right to left
61        while (rightmostIndex > right) {
62            const position = numBuildings - heightPosition(heights[rightmostIndex]) + 1;
63            update(position, rightmostIndex);
64            --rightmostIndex;
65        }
66
67        // Directly comparing heights if buildings are at the same position or right is taller
68        if (left === right || heights[left] < heights[right]) {
69            results[queryIndex] = right;
70        } else {
71            const position = numBuildings - heightPosition(heights[left]);
72            results[queryIndex] = query(position);
73        }
74    }
75    return results;
76}
77
78// Note that before calling `update` or `query`, you should always call `initialize` with the number of buildings.
79

Time and Space Complexity

The given Python code defines a class BinaryIndexedTree (BIT) for efficient updates and queries over prefix minimums, and a class Solution that uses this data structure to answer a set of building height queries.

Time Complexity:

  1. Initialization of BIT: The __init__ of the BinaryIndexedTree runs in O(n) time because it initializes an array c with n + 1 elements each set to inf.

  2. BIT Update: The update method runs in O(log n) time. This is because in the worst case, it must traverse the height of the tree, which corresponds to the number of bits in the index x, which is at most log2(n).

  3. BIT Query: The query method also runs in O(log n) time for the same reason as update; it traverses up the tree.

In the Solution class:

  1. Preprocessing Steps:

    • Sorting heights to create s: O(n log n).
    • Sorting queries based on right endpoints in decreasing order: O(m log m).
  2. Main Algorithm: The loop iterates through sorted queries worst-case m times. Within each iteration:

    • The update operation on the BIT is performed O(n-r) times for all iterations, where r is the right endpoint of queries (in the worst case, for each unique height). Each update operation takes O(log n), so the total time is O((n-r) log n).
    • The query operation takes O(log n) time.

To calculate the overall time complexity, we combine the preprocessing steps with the main algorithm:

  • Initialization: O(n)
  • Sorting heights and queries: O(n log n) + O(m log m)
  • Main Loop: O(m (n-r) log n) (amortized over all updates and queries).

Combining these, the dominant term is the main loop, assuming that n-r is not constantly small, yielding:

  • Total Time Complexity: O(m (n-r) log n).

Space Complexity:

  1. BIT Storage: O(n) for the array c.
  2. Auxiliary Space:
    • Set s created from heights: O(n) as it can contain all unique heights.
    • Sorted queries: O(m) additional space for the sorted order of queries.

Therefore, the total space complexity is:

  • Total Space Complexity: O(n + m), which simplifies to O(n) if n is larger than m.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the relationship between a tree and a graph?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄