LeetCode Entry

1306. Jump Game III

17.05.2026 medium 2026 kotlin rust

Can reach 0 by jumping +a[i] - a[i]

1306. Jump Game III medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1362

Problem TLDR

Can reach 0 by jumping +a[i] - a[i]

Intuition

• Union-Find would not work - we have a strictly directed edges in graph
• BFS/DFS works

Approach

• use array itself as a visited set
• use ‘camicadze’ value to make it out of range and make less checks

Complexity

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

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

Code

    fun canReach(a: IntArray, s: Int):Boolean = s in a.indices&&
    a[s].let{x->a[s]=a.size;x==0||canReach(a,s-x)||canReach(a,s+x)}

    pub fn can_reach(mut a: Vec<i32>, s: i32) -> bool {
        let mut q = vec![s];
        while let Some(i) = q.pop() {
            let Some(x) = a.get_mut(i as usize) else {continue};
            if *x == 0 { return true }
            q.extend([i-*x,i+*x]); *x += 100000
        } false
    }