LeetCode in Kotlin

3620. Network Recovery Pathways

Hard

You are given a directed acyclic graph of n nodes numbered from 0 to n − 1. This is represented by a 2D array edges of length m, where edges[i] = [ui, vi, costi] indicates a one‑way communication from node ui to node vi with a recovery cost of costi.

Some nodes may be offline. You are given a boolean array online where online[i] = true means node i is online. Nodes 0 and n − 1 are always online.

A path from 0 to n − 1 is valid if:

For each valid path, define its score as the minimum edge‑cost along that path.

Return the maximum path score (i.e., the largest minimum-edge cost) among all valid paths. If no valid path exists, return -1.

Example 1:

Input: edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], online = [true,true,true,true], k = 10

Output: 3

Explanation:

Example 2:

Input: edges = [[0,1,7],[1,4,5],[0,2,6],[2,3,6],[3,4,2],[2,4,6]], online = [true,true,true,false,true], k = 12

Output: 6

Explanation:

Constraints:

Solution

import java.util.LinkedList
import java.util.Queue
import kotlin.math.max

class Solution {
    private fun topologicalSort(n: Int, g: Array<ArrayList<Int>>): List<Int> {
        val indeg = IntArray(n)
        for (i in 0 until n) {
            for (adjNode in g[i]) {
                indeg[adjNode]++
            }
        }
        val q: Queue<Int> = LinkedList()
        val ts = ArrayList<Int>()
        for (i in 0 until n) {
            if (indeg[i] == 0) {
                q.offer(i)
            }
        }
        while (q.isNotEmpty()) {
            val u = q.poll()
            ts.add(u)
            for (v in g[u]) {
                indeg[v]--
                if (indeg[v] == 0) {
                    q.offer(v)
                }
            }
        }
        return ts
    }

    private fun check(
        x: Int,
        n: Int,
        adj: Array<ArrayList<IntArray>>,
        ts: List<Int>,
        online: BooleanArray,
        k: Long,
    ): Boolean {
        val d = LongArray(n)
        d.fill(Long.MAX_VALUE)
        d[0] = 0
        for (u in ts) {
            if (d[u] != Long.MAX_VALUE) {
                for (p in adj[u]) {
                    val v = p[0]
                    val c = p[1]
                    if (c < x || !online[v]) {
                        continue
                    }
                    if (d[u] + c < d[v]) {
                        d[v] = d[u] + c
                    }
                }
            }
        }
        return d[n - 1] <= k
    }

    fun findMaxPathScore(edges: Array<IntArray>, online: BooleanArray, k: Long): Int {
        val n = online.size
        // Adjacency list for graph with edge weights
        val adj = Array<ArrayList<IntArray>>(n) { ArrayList() }
        val g = Array<ArrayList<Int>>(n) { ArrayList() }
        for (e in edges) {
            val u = e[0]
            val v = e[1]
            val c = e[2]
            adj[u].add(intArrayOf(v, c))
            g[u].add(v)
        }
        val ts = topologicalSort(n, g)
        if (!check(0, n, adj, ts, online, k)) {
            return -1
        }
        var l = 0
        var h = 0
        for (e in edges) {
            h = max(h, e[2])
        }
        while (l < h) {
            val md = l + (h - l + 1) / 2
            if (check(md, n, adj, ts, online, k)) {
                l = md
            } else {
                h = md - 1
            }
        }
        return l
    }
}