LeetCode Entry

1345. Jump Game IV

18.05.2026 hard 2026 kotlin rust

Min steps to reach end jumping to same value or left or right

1345. Jump Game IV hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1363

Problem TLDR

Min steps to reach end jumping to same value or left or right

Intuition

group by value and do BFS

Approach

• remove visited groups
• mark visited early

Complexity

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

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

Code

    fun minJumps(a: IntArray): Int {
        val g = HashMap(a.indices.groupBy{a[it]}); var t = -1
        val q = ArrayDeque(listOf(0)); val v = hashSetOf(0)
        while (q.size > 0 && ++t>=0) for (x in 1..q.size) {
            val i = q.removeFirst(); if (i == a.size-1) return t
            for (j in (g.remove(a[i])?:setOf())+(i-1)+(i+1))
                if (j in a.indices && v.add(j)) q += j
        }
        return a.size-1
    }

    pub fn min_jumps(a: Vec<i32>) -> i32 {
        let mut g = (0..a.len()).into_group_map_by(|&i| a[i]);
        let (mut q, mut v, mut t) = (vec![0], vec![0;a.len()], 0);
        loop { let mut w = vec![]; for i in q {
            if i == a.len()-1 { return t }
            for j in g.remove(&a[i]).into_iter().flatten().chain([i-1,i+1]) {
                if j < a.len() && v[j] < 1 { v[j] = 1; w.push(j) }
            }
        } q = w; t += 1 }
    }