Home >Backend Development >PHP Tutorial >Find Building Where Alice and Bob Can Meet
2940. Find Building Where Alice and Bob Can Meet
Difficulty: Hard
Topics: Array, Binary Search, Stack, Binary Indexed Tree, Segment Tree, Heap (Priority Queue), Monotonic Stack
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] = [ai, bi]. On the ith query, Alice is in building ai while Bob is in building bi.
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.
Example 1:
Example 2:
Constraints:
Hint:
Solution:
The problem requires determining the leftmost building where Alice and Bob can meet given their starting buildings and movement rules. Each query involves finding a meeting point based on building heights. This is challenging due to the constraints on movement and the need for efficient computation.
Observations:
Optimization Using Monotonic Stack:
Query Sorting:
Binary Search on Stack:
Preprocess Queries:
Iterate Through Queries:
Binary Search on Stack:
Restore Original Order:
Return Results.
Let's implement this solution in PHP: 2940. Find Building Where Alice and Bob Can Meet
<?php /** * @param Integer[] $heights * @param Integer[][] $queries * @return Integer[] */ function leftmostBuildingQueries($heights, $queries) { ... ... ... /** * go to ./solution.php */ } /** * @param $queries * @return array */ private function getIndexedQueries($queries) { ... ... ... /** * go to ./solution.php */ } /** * @param $stack * @param $a * @param $heights * @return mixed|null */ private function findUpperBound($stack, $a, $heights) { ... ... ... /** * go to ./solution.php */ } class IndexedQuery { public $queryIndex; public $a; // Alice's index public $b; // Bob's index /** * @param $queryIndex * @param $a * @param $b */ public function __construct($queryIndex, $a, $b) { $this->queryIndex = $queryIndex; $this->a = $a; $this->b = $b; } } // Test the function $heights = [6, 4, 8, 5, 2, 7]; $queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]]; print_r(leftmostBuildingQueries($heights, $queries)); $heights = [5, 3, 8, 2, 6, 1, 4, 6]; $queries = [[0, 7], [3, 5], [5, 2], [3, 0], [1, 6]]; print_r(leftmostBuildingQueries($heights, $queries)); ?>
Sort Queries:
Build Monotonic Stack:
Query Processing:
[2, 5, -1, 5, 2]
Overall: O(N Q log (Q N)).
Input:
$heights = [6, 4, 8, 5, 2, 7]; $queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];
Output:
print_r(findBuilding($heights, $queries)); // [2, 5, -1, 5, 2]
This approach efficiently handles large constraints by leveraging a monotonic stack and binary search. It ensures optimal query processing while maintaining correctness.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
The above is the detailed content of Find Building Where Alice and Bob Can Meet. For more information, please follow other related articles on the PHP Chinese website!