45. Jump Game II Medium

1/**
2 * [45] Jump Game II
3 *
4 * Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
5 * Each element in the array represents your maximum jump length at that position.
6 * Your goal is to reach the last index in the minimum number of jumps.
7 * You can assume that you can always reach the last index.
8 *  
9 * Example 1:
10 * 
11 * Input: nums = [2,3,1,1,4]
12 * Output: 2
13 * Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
14 * 
15 * Example 2:
16 * 
17 * Input: nums = [2,3,0,1,4]
18 * Output: 2
19 * 
20 *  
21 * Constraints:
22 * 
23 * 1 <= nums.length <= 10^4
24 * 0 <= nums[i] <= 1000
25 * 
26 */
27pub struct Solution {}
28
29// problem: https://leetcode.com/problems/jump-game-ii/
30// discuss: https://leetcode.com/problems/jump-game-ii/discuss/?currentPage=1&orderBy=most_votes&query=
31
32// submission codes start here
33
34use std::cmp;
35impl Solution {
36    pub fn jump(nums: Vec<i32>) -> i32 {
37        let (mut min_step, mut max, mut current_reach) = (0, 0, 0);
38        for i in 0..nums.len() - 1 {
39            max = cmp::max(max, i as i32 + nums[i]);
40            if i == current_reach {
41                min_step += 1;
42                current_reach = max as usize;
43            }
44        }
45        min_step
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_45() {
57        assert_eq!(Solution::jump(vec![2,3,1,1,4]), 2);
58    }
59}
60