Java solution O(n)


  • 0
    W

    This solution compute all distance in steps until found the destination.
    Less tricky to understand, just a very boring solution.

    import java.util.Arrays;
    
    public class Solution {
        public int jump(int[] nums) {
            if (nums.length == 1) return 0;
            int[] dist = new int[nums.length];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[0] = 0;
            int best_reach = 0;
            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = best_reach+1;
                     j <= i + nums[i] && j < nums.length; j++) {
                    best_reach = Math.max(best_reach, j);
                    dist[j] = Math.min(dist[i] + 1, dist[j]);
                    if (j==nums.length-1)
                        return dist[j];
                }
            }
    
            return 0;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.