DMITRII’s Substack

Share this post

Leetcode daily # 30.04.2023

dmitriisamoilenko.substack.com

Leetcode daily # 30.04.2023

[1579. Remove Max Number of Edges to Keep Graph Fully Traversable]

DMITRII SAMOILENKO
Apr 30, 2023
Share
Share this post

Leetcode daily # 30.04.2023

dmitriisamoilenko.substack.com

30.04.2023

1579. Remove Max Number of Edges to Keep Graph Fully Traversable hard

fun IntArray.root(a: Int): Int {
    var x = a
    while (this[x] != x) x = this[x]
    this[a] = x
    return x
}
fun IntArray.union(a: Int, b: Int): Boolean {
    val rootA = root(a)
    val rootB = root(b)
    if (rootA != rootB) this[rootB] = rootA
    return rootA != rootB
}
fun IntArray.connected(a: Int, b: Int) = root(a) == root(b)
fun maxNumEdgesToRemove(n: Int, edges: Array<IntArray>): Int {
    val uf1 = IntArray(n + 1) { it }
    val uf2 = IntArray(n + 1) { it }
    var skipped = 0
    edges.forEach { (type, a, b) ->
        if (type == 3) {
            uf1.union(a, b)
            if (!uf2.union(a, b)) skipped++
        }
    }
    edges.forEach { (type, a, b) ->
        if (type == 1 && !uf1.union(a, b)) skipped++
    }
    edges.forEach { (type, a, b) ->
        if (type == 2 && !uf2.union(a, b)) skipped++
    }
    for (i in 2..n)
    if (!uf1.connected(i - 1, i) || !uf2.connected(i - 1, i)) return -1
    return skipped
}

blog post

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

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/196

Intuition

After connecting all type 3 nodes, we can skip already connected nodes for Alice and for Bob. To detect if all the nodes are connected, we can just check if all nodes connected to one particular node.

Approach

Use separate Union-Find objects for Alice and for Bob

Complexity

  • Time complexity:
    O(n), as root and union operations take < 5 for any n <= Int.MAX.

  • 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 # 30.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