LeetCode in Kotlin
3924. Minimum Threshold Path With Limited Heavy Edges
Hard
There is an undirected weighted graph with n nodes labeled from 0 to n - 1.
The graph is represented by a 2D integer array edges, where each edge edges[i] = [ui, vi, wi] indicates that there is an undirected edge between nodes ui and vi with weight wi.
You are also given integers source, target and k.
A threshold value determines whether an edge is considered light or heavy:
-
An edge is light if its weight is less than or equal to
threshold. -
An edge is heavy if its weight is greater than
threshold.
A path from source to target is valid if it contains at most k heavy edges.
Return the minimum integer threshold such that at least one valid path exists from source to target. If no such path exists, return -1.
Example 1:
Input: n = 6, edges = [[0,1,5],[1,2,3],[3,4,4],[4,5,1],[1,4,2]], source = 0, target = 3, k = 1
Output: 4
Explanation:
The minimum threshold such that a path from node 0 to node 3 uses at most 1 heavy edge is 4.
-
Light edges:
[1, 2, 3],[3, 4, 4],[4, 5, 1],[1, 4, 2] -
Heavy edges:
[0, 1, 5]
A valid path is 0 → 1 → 4 → 3. It uses only 1 heavy edge ([0, 1, 5]), which satisfies the limit k = 1.
Any smaller threshold would make it impossible to reach node 3 without exceeding 1 heavy edge.
Example 2:
Input: n = 6, edges = [[0,1,3],[1,2,4],[3,4,5],[4,5,6]], source = 0, target = 4, k = 1
Output: -1
Explanation:
There is no path from node 0 to node 4. Since the target cannot be reached, the output is -1.
Example 3:
Input: n = 4, edges = [[0,1,2],[1,2,2],[2,3,2],[3,0,2]], source = 0, target = 0, k = 0
Output: 0
Explanation:
The source and target are the same node. No edges need to be traversed, so the minimum threshold is 0.
Constraints:
1 <= n <= 1030 <= edges.length <= 103edges[i] = [ui, vi, wi]0 <= ui, vi <= n - 11 <= wi <= 1090 <= source, target <= n - 10 <= k <= edges.length
Solution
class Solution {
private lateinit var head: IntArray
private lateinit var to: IntArray
private lateinit var weight: IntArray
private lateinit var next: IntArray
private var n = 0
private var source = 0
private var target = 0
private var k = 0
fun minimumThreshold(n: Int, edges: Array<IntArray>, source: Int, target: Int, k: Int): Int {
if (source == target) {
return 0
}
this.n = n
this.source = source
this.target = target
this.k = k
// make adj list (you dont have to do this fancy version, standard adj list works)
val m = edges.size
this.head = IntArray(n)
this.to = IntArray(m shl 1)
this.weight = IntArray(m shl 1)
this.next = IntArray(m shl 1)
head.fill(-1)
for (i in 0..<m) {
val a = edges[i][0]
val b = edges[i][1]
val c = edges[i][2]
to[i shl 1] = b
next[i shl 1] = head[a]
head[a] = i shl 1
to[i shl 1 or 1] = a
next[i shl 1 or 1] = head[b]
head[b] = i shl 1 or 1
weight[i shl 1 or 1] = c
weight[i shl 1] = weight[i shl 1 or 1]
}
// check if it's possible to reach the target at all
if (!check(Int.MAX_VALUE)) {
return -1
}
if (k == m) {
return 0
}
var left = 0
var right = 0
// set right pointer to max edge weight, cuz any threshold larger than that is pointless
for (edge in edges) {
if (edge[2] > right) {
right = edge[2]
}
}
// binary search on the answer
while (left < right) {
val mid = left + right ushr 1
if (check(mid)) {
right = mid
} else {
left = mid + 1
}
}
return left
}
private fun check(threshold: Int): Boolean {
// 0-1 BFS
val dist = IntArray(n)
dist.fill(k + 1)
dist[source] = 0
val queue = java.util.ArrayDeque<Int>(n)
queue.add(source)
while (queue.isNotEmpty()) {
val current: Int = queue.poll()!!
if (current == target) {
return true
}
val currentDist = dist[current]
// go through each adj node (a regular adj list works here as well)
var i = head[current]
while (i != -1) {
val node = to[i]
val newWeight = if (weight[i] > threshold) 1 else 0
val newDist = newWeight + currentDist
if (newDist < dist[node]) {
dist[node] = newDist
if (newWeight == 0) {
queue.addFirst(node)
} else {
queue.addLast(node)
}
}
i = next[i]
}
}
return false
}
}