LeetCode Entry

2492. Minimum Score of a Path Between Two Cities

04.07.2026 medium 2026 kotlin rust

Min in connected edges

2492. Minimum Score of a Path Between Two Cities medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1410

Problem TLDR

Min in connected edges

Intuition

Use Union-Find to find the connected group.

Approach

• uf path compression: u[x]=f(u[x]) is enough speed up
• don’t forget to initialize with own indices u = 1..n

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun minScore(n: Int, r: Array<IntArray>): Int {
        val u = IntArray(n+1){it}
        fun f(x: Int): Int = if (x==u[x])x else {u[x]=f(u[x]);u[x]}
        for ((a,b) in r) u[f(a)] = f(b)
        return r.minOf{(a,b,d) -> if (f(a)==f(1)) d else 999999}
    }

    pub fn min_score(n: i32, r: Vec<Vec<i32>>) -> i32 {
        let mut u: Vec<_> = (0..=n as usize).collect();
        let mut f = |x: i32, u: &mut [usize]| {
            let mut x = x as usize; while u[x] != x { u[x] = u[u[x]]; x = u[x] }; x };
        for e in &r { let (a,b) = (f(e[0], &mut u), f(e[1], &mut u)); u[a] = b }
        r.iter().filter(|e| f(e[0], &mut u) == f(1, &mut u)).map(|e| e[2]).min().unwrap()
    }