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] = [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:
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 * 1041 <= heights[i] <= 1091 <= queries.length <= 5 * 104queries[i] = [ai, bi]0 <= ai, bi <= heights.length - 1
Solutions#
Solution 1: Binary Indexed Tree#
Let’s denote $queries[i] = [l_i, r_i]$, where $l_i \le r_i$. If $l_i = r_i$ or $heights[l_i] < heights[r_i]$, then the answer is $r_i$. Otherwise, we need to find the smallest $j$ among all $j > r_i$ and $heights[j] > heights[l_i]$.
We can sort $queries$ in descending order of $r_i$, and use a pointer $j$ to point to the current index of $heights$ being traversed.
Next, we traverse each query $queries[i] = (l, r)$. For the current query, if $j > r$, then we loop to insert $heights[j]$ into the binary indexed tree. The binary indexed tree maintains the minimum index of the suffix height (after discretization). Then, we judge whether $l = r$ or $heights[l] < heights[r]$. If it is, then the answer to the current query is $r$. Otherwise, we query the minimum index of $heights[l]$ in the binary indexed tree, which is the answer to the current query.
The time complexity is $O((n + m) \times \log n + m \times \log m)$, and the space complexity is $O(n + m)$. Where $n$ and $m$ are the lengths of $heights$ and $queries$ respectively.
Similar problems:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class BinaryIndexedTree:
__slots__ = ["n", "c"]
def __init__(self, n: int):
self.n = n
self.c = [inf] * (n + 1)
def update(self, x: int, v: int):
while x <= self.n:
self.c[x] = min(self.c[x], v)
x += x & -x
def query(self, x: int) -> int:
mi = inf
while x:
mi = min(mi, self.c[x])
x -= x & -x
return -1 if mi == inf else mi
class Solution:
def leftmostBuildingQueries(
self, heights: List[int], queries: List[List[int]]
) -> List[int]:
n, m = len(heights), len(queries)
for i in range(m):
queries[i] = [min(queries[i]), max(queries[i])]
j = n - 1
s = sorted(set(heights))
ans = [-1] * m
tree = BinaryIndexedTree(n)
for i in sorted(range(m), key=lambda i: -queries[i][1]):
l, r = queries[i]
while j > r:
k = n - bisect_left(s, heights[j]) + 1
tree.update(k, j)
j -= 1
if l == r or heights[l] < heights[r]:
ans[i] = r
else:
k = n - bisect_left(s, heights[l])
ans[i] = tree.query(k)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| class BinaryIndexedTree {
private final int inf = 1 << 30;
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
Arrays.fill(c, inf);
}
public void update(int x, int v) {
while (x <= n) {
c[x] = Math.min(c[x], v);
x += x & -x;
}
}
public int query(int x) {
int mi = inf;
while (x > 0) {
mi = Math.min(mi, c[x]);
x -= x & -x;
}
return mi == inf ? -1 : mi;
}
}
class Solution {
public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
int n = heights.length;
int m = queries.length;
for (int i = 0; i < m; ++i) {
if (queries[i][0] > queries[i][1]) {
queries[i] = new int[] {queries[i][1], queries[i][0]};
}
}
Integer[] idx = new Integer[m];
for (int i = 0; i < m; ++i) {
idx[i] = i;
}
Arrays.sort(idx, (i, j) -> queries[j][1] - queries[i][1]);
int[] s = heights.clone();
Arrays.sort(s);
int[] ans = new int[m];
int j = n - 1;
BinaryIndexedTree tree = new BinaryIndexedTree(n);
for (int i : idx) {
int l = queries[i][0], r = queries[i][1];
while (j > r) {
int k = n - Arrays.binarySearch(s, heights[j]) + 1;
tree.update(k, j);
--j;
}
if (l == r || heights[l] < heights[r]) {
ans[i] = r;
} else {
int k = n - Arrays.binarySearch(s, heights[l]);
ans[i] = tree.query(k);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| class BinaryIndexedTree {
private:
int inf = 1 << 30;
int n;
vector<int> c;
public:
BinaryIndexedTree(int n) {
this->n = n;
c.resize(n + 1, inf);
}
void update(int x, int v) {
while (x <= n) {
c[x] = min(c[x], v);
x += x & -x;
}
}
int query(int x) {
int mi = inf;
while (x > 0) {
mi = min(mi, c[x]);
x -= x & -x;
}
return mi == inf ? -1 : mi;
}
};
class Solution {
public:
vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
int n = heights.size(), m = queries.size();
for (auto& q : queries) {
if (q[0] > q[1]) {
swap(q[0], q[1]);
}
}
vector<int> idx(m);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j) {
return queries[j][1] < queries[i][1];
});
vector<int> s = heights;
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
vector<int> ans(m);
int j = n - 1;
BinaryIndexedTree tree(n);
for (int i : idx) {
int l = queries[i][0], r = queries[i][1];
while (j > r) {
int k = s.end() - lower_bound(s.begin(), s.end(), heights[j]) + 1;
tree.update(k, j);
--j;
}
if (l == r || heights[l] < heights[r]) {
ans[i] = r;
} else {
int k = s.end() - lower_bound(s.begin(), s.end(), heights[l]);
ans[i] = tree.query(k);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| const inf int = 1 << 30
type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) BinaryIndexedTree {
c := make([]int, n+1)
for i := range c {
c[i] = inf
}
return BinaryIndexedTree{n: n, c: c}
}
func (bit *BinaryIndexedTree) update(x, v int) {
for x <= bit.n {
bit.c[x] = min(bit.c[x], v)
x += x & -x
}
}
func (bit *BinaryIndexedTree) query(x int) int {
mi := inf
for x > 0 {
mi = min(mi, bit.c[x])
x -= x & -x
}
if mi == inf {
return -1
}
return mi
}
func leftmostBuildingQueries(heights []int, queries [][]int) []int {
n, m := len(heights), len(queries)
for _, q := range queries {
if q[0] > q[1] {
q[0], q[1] = q[1], q[0]
}
}
idx := make([]int, m)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool { return queries[idx[j]][1] < queries[idx[i]][1] })
s := make([]int, n)
copy(s, heights)
sort.Ints(s)
ans := make([]int, m)
tree := NewBinaryIndexedTree(n)
j := n - 1
for _, i := range idx {
l, r := queries[i][0], queries[i][1]
for ; j > r; j-- {
k := n - sort.SearchInts(s, heights[j]) + 1
tree.update(k, j)
}
if l == r || heights[l] < heights[r] {
ans[i] = r
} else {
k := n - sort.SearchInts(s, heights[l])
ans[i] = tree.query(k)
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| class BinaryIndexedTree {
private n: number;
private c: number[];
private inf: number = 1 << 30;
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(this.inf);
}
update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] = Math.min(this.c[x], v);
x += x & -x;
}
}
query(x: number): number {
let mi = this.inf;
while (x > 0) {
mi = Math.min(mi, this.c[x]);
x -= x & -x;
}
return mi === this.inf ? -1 : mi;
}
}
function leftmostBuildingQueries(heights: number[], queries: number[][]): number[] {
const n = heights.length;
const m = queries.length;
for (const q of queries) {
if (q[0] > q[1]) {
[q[0], q[1]] = [q[1], q[0]];
}
}
const idx: number[] = Array(m)
.fill(0)
.map((_, i) => i);
idx.sort((i, j) => queries[j][1] - queries[i][1]);
const tree = new BinaryIndexedTree(n);
const ans: number[] = Array(m).fill(-1);
const s = [...heights];
s.sort((a, b) => a - b);
const search = (x: number) => {
let [l, r] = [0, n];
while (l < r) {
const mid = (l + r) >> 1;
if (s[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
let j = n - 1;
for (const i of idx) {
const [l, r] = queries[i];
while (j > r) {
const k = n - search(heights[j]) + 1;
tree.update(k, j);
--j;
}
if (l === r || heights[l] < heights[r]) {
ans[i] = r;
} else {
const k = n - search(heights[l]);
ans[i] = tree.query(k);
}
}
return ans;
}
|
