#### Discover more from DMITRII’s Substack

# 29.04.2023

1697. Checking Existence of Edge Length Limited Paths hard

```
fun distanceLimitedPathsExist(n: Int, edgeList: Array<IntArray>, queries: Array<IntArray>): BooleanArray {
val uf = IntArray(n) { it }
fun root(x: Int): Int {
var n = x
while (uf[n] != n) n = uf[n]
uf[x] = n
return n
}
fun union(a: Int, b: Int) {
val rootA = root(a)
val rootB = root(b)
if (rootA != rootB) uf[rootB] = rootA
}
val indices = queries.indices.sortedWith(compareBy( { queries[it][2] } ))
edgeList.sortWith(compareBy( { it[2] } ))
var edgePos = 0
val res = BooleanArray(queries.size)
indices.forEach { ind ->
val (qfrom, qto, maxDist) = queries[ind]
while (edgePos < edgeList.size) {
val (from, to, dist) = edgeList[edgePos]
if (dist >= maxDist) break
union(from, to)
edgePos++
}
res[ind] = root(qfrom) == root(qto)
}
return res
}
```

#### Join me on Telegram

https://t.me/leetcode_daily_unstoppable/195

#### Intuition

The naive approach is to do BFS for each query, obviously gives TLE as it takes O(n^2) time.

Using the hint, we can use somehow the sorted order of the queries. If we connect every two nodes with `dist < query.dist`

we have connected groups with all nodes reachable inside them. The best data structure for union and finding connected groups is the Union-Find.

To avoid iterating `edgeList`

every time, we can sort it too and take only available distances.

#### Approach

for better time complexity, compress the Union-Find path = n

track the

`edgePos`

- a position in a sorted`edgeList`

make separate

`indices`

list to sort queries without losing the order

#### Complexity

Time complexity:

O(nlog(n)), time complexity for`root`

and`union`

operations is an inverse Ackerman function and`< 5`

for every possible number in Int.Space complexity:

O(n)