No BFS


  • 0
    K

    Sample array {4,1,1,1,3,1,1}
    The first jump is 4. This implies that starting from 0 until 4th index, the min number of jumps to be taken is 1. While we travel from index 0 to 4, we also track the next max jump.
    At index 0, max is 4
    At index 1, max is 3 (max(3,1))
    At index 2, max is 2 (max(2,1))
    At index 3, max is 1 (max(1,1))
    At index 4, max is 3 (max(0,3))
    Total number of min steps to reach 0 to 4th index is 1.
    At index 5, max is 2 (max(2,1))
    At index 6, max is 1 (max(1,1))
    Total number of min steps to reach 0 to 6th index is 2.

    public int jump(int[] jumps) {
                    int j = jumps[0];
    		int max = jumps[0];
    		int steps = 0;
    		int i = 0;
                    // loop through the array
    		while(i < jumps.length-1) {
                            // loop until the current steps is not 0. While looping, track the next max steps.
    			while(j>0 && i < jumps.length-1) {
    				j--;				
    				max = Math.max(jumps[++i],max-1);
    			}
    			steps++;
    			j = max;
    			if(j==0) break;
    		}
    		return (i==jumps.length-1)?steps:0;
        }
    

Log in to reply
 

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