1306. Jump Game III Medium

1/**
2 * [1306] Jump Game III
3 *
4 * Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.
5 * Notice that you can not jump outside of the array at any time.
6 *  
7 * Example 1:
8 * 
9 * Input: arr = [4,2,3,0,3,1,2], start = 5
10 * Output: true
11 * Explanation: 
12 * All possible ways to reach at index 3 with value 0 are: 
13 * index 5 -> index 4 -> index 1 -> index 3 
14 * index 5 -> index 6 -> index 4 -> index 1 -> index 3 
15 * 
16 * Example 2:
17 * 
18 * Input: arr = [4,2,3,0,3,1,2], start = 0
19 * Output: true 
20 * Explanation: 
21 * One possible way to reach at index 3 with value 0 is: 
22 * index 0 -> index 4 -> index 1 -> index 3
23 * 
24 * Example 3:
25 * 
26 * Input: arr = [3,0,2,1,2], start = 2
27 * Output: false
28 * Explanation: There is no way to reach at index 1 with value 0.
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	1 <= arr.length <= 5 * 10^4
34 * 	0 <= arr[i] < arr.length
35 * 	0 <= start < arr.length
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/jump-game-iii/
41// discuss: https://leetcode.com/problems/jump-game-iii/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn can_reach(arr: Vec<i32>, start: i32) -> bool {
47        false
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_1306() {
59    }
60}
61