DMITRII’s Substack

Share this post

Leetcode daily # 29.04.2023

dmitriisamoilenko.substack.com

Leetcode daily # 29.04.2023

[1697. Checking Existence of Edge Length Limited Paths]

DMITRII SAMOILENKO
Apr 29, 2023
Share
Share this post

Leetcode daily # 29.04.2023

dmitriisamoilenko.substack.com

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
}

blog post

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)

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

Share
Share this post

Leetcode daily # 29.04.2023

dmitriisamoilenko.substack.com
Previous
Next
Comments
Top
New

No posts

Ready for more?

© 2023 DMITRII SAMOILENKO
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing