AC Java O(N solution) using Concept of BFS and easy to understand


  • 1
    R

    The solution to this problem can be thought of as a bfs traversal. We can have two variables that indicate the boundaries, namely currentBoundary and nextBoundary. We also store a variable to denote the maximum index that we can reach from a particular level.

    Whenever the index crosses the currentBoundary, we increase the number of steps by 1. If we continue iteration like this till the end of the array, we will have the minimum number of steps required to jump to the final index. Here is my accepted code

    public int jump(int[] nums) {
            
            if(nums.length <= 1){
                return 0;
            }
            
            int currentBoundary = 0;
            int nextBoundary = 0;
            int steps = 0;
            
            for(int i=0;i < nums.length;i++ ){
                
                if(i > currentBoundary){
                    currentBoundary = nextBoundary;
                    ++steps;
                }
                
                if(i+nums[i] > nextBoundary){
                    nextBoundary = i+nums[i];
                }
                
            }
            
            return steps;
        }
    

  • 0
    I

    I had a similar idea that I implemented in my program. Basically it calculates the maximum jump distance for each index and then uses that to count the number of jumps without actually knowing the optimal path.

    public int jump(int[] nums) {
            int[] maxReach=new int[nums.length];
            //finds the furthest index that can be reached using indexes before or at i
            //for example, [3,1,4,1,1,2,2,1,1] would be [3,3,6,6,6,7,8,8,9]
            maxReach[0]=nums[0];
            for (int i=1; i<maxReach.length; i++){
                maxReach[i]=maxReach[i-1]>nums[i]+i? maxReach[i-1]:nums[i]+i;
            }
            // finds the optimal number of jumps using the furthest reach calculated above
            int index=0;
            int count=0;
            while (index<maxReach.length-1){
                count++;
                index=maxReach[index];
            }
            return count;
        }

Log in to reply
 

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