O(n), BFS solution


  • 108
    E

    I try to change this problem to a BFS problem, where nodes in level i are all the nodes that can be reached in i-1th jump. for example. 2 3 1 1 4 , is
    2||
    3 1||
    1 4 ||

    clearly, the minimum jump of 4 is 2 since 4 is in level 3. my ac code.

     int jump(int A[], int n) {
    	 if(n<2)return 0;
    	 int level=0,currentMax=0,i=0,nextMax=0;
    
    	 while(currentMax-i+1>0){		//nodes count of current level>0
    		 level++;
    		 for(;i<=currentMax;i++){	//traverse current level , and update the max reach of next level
    			nextMax=max(nextMax,A[i]+i);
    			if(nextMax>=n-1)return level;   // if last element is in level+1,  then the min jump=level 
    		 }
    		 currentMax=nextMax;
    	 }
    	 return 0;
     }

  • 8
    W

    Hi, your idea is nice, but your code does not handle the case when u can not jump to the end.
    (e.g. A={3,0,0,0,4} or A={0,5} etc.) I slightly modify your code to return INT_MAX in that case

     int jump(int A[], int n) { //O(N)
        	 if(n<2) return 0;
        	 int level=0,currentMax=0,i=0,nextMax=0;
        	 
        	 while(currentMax-i+1>0){ //nodes count of current level>0
        		 level++;
        		 for(;i<=currentMax;i++){ //traverse current level , and update the max reach of next level
        			nextMax=max(nextMax,A[i]+i);
        			if(nextMax>=n-1) return level;// if last element is in level+1,  then the min jump=level
        		 }
        
        		 if(currentMax==nextMax) return INT_MAX; //***cannot move forward from this level
        
        		 currentMax=nextMax;
        	 }	
        }

  • 2
    E

    My python solution is based on the same idea, but without BFS,

    class Solution:
        # @param A, a list of integers
        # @return an integer
        def jump(self, A):
            if len(A) <= 1:
                return 0
            step, max_range, next_range = 1, A[0], A[0]
            for i in xrange(1,len(A)):
                if max_range >= len(A)-1:
                    return step
                if i > max_range:
                    max_range = next_range
                    step += 1
                next_range = max(next_range, i + A[i])
            return step

  • 1

    Hi, wei31. Very great observation in the code if(currentMax==nextMax) return INT_MAX;. I think the problem you propose is good to be taken into consideration.


  • 1
    H

    That was a great solution! I used want to solved this problem by bfs, and i used the queue to store every index,then bfs every index, util find the last one . It was time limited, then I abandoned such methd.
    But you are successed by BFS. That was proved my mind was right,but not skilled in the bfs coding.
    Thank you!


  • 2
    Y

    Why not directly change return 0; into return Integer.MAX_VALUE;?


  • 1
    J

    I came up with similar solutions, but is it really o(n)?


  • 3
    T

    a concise solution

    int jump(vector<int>& nums) {
            int i(0), j(1), steps(0), N(nums.size());
            while(j < N){
                int endj = min(nums[i]+i+1, N);
                while(j < endj){
                    if(nums[j] + j > nums[i] + i) i = j;
                    j++;
                }
                steps++;
            }
            return steps;
        }

  • 5
    H

    while condition could be written as

    while(i <= currentMax)
    

    This is more concise and easier to understand


  • 0
    J

    O(n), not o(n). That latter would imply it is sub-linear, which is not the case.


  • 0
    M

    @tju_xu97 Can you explain your code?


  • 1

    you don't need to check the corner case like n < 2.

    class Solution {
    public:
    int jump(vector<int>& nums) {
    int level = 0, curMax = 0, nextMax = 0;
    int i = 0;
    while(i < nums.size()){
    if(curMax + 1 >= nums.size())
    return level;
    level++;
    for(; i <= curMax; i++){
    nextMax = max(nextMax, nums[i] + i);
    }
    curMax = nextMax;
    }
    return level;
    }
    };


  • 1

    Here is my cpp program, the same idea.

    int jump(vector<int>& nums) 
    {
    	if (nums.size() <= 1)
    		return 0;
    	int right = 0 + nums[0], step = 1;
            int cover = right;
    	for (int i = 0; i <= right; ++i)
    	{
                    if (right >= nums.size() - 1)
    			return step;
    		if (nums[i] + i > cover)
    			cover = nums[i] + i;
    		if (i == right)
    		{
    			right = cover;
    			++step;
    		}
    	}
    	return 0;
    }
    

  • 0
    R
    This post is deleted!

  • 0
    Z

    nice~how do you get it? I find it difficulty to get this solution~


  • 0

    Similar Idea.

    public int jump(int[] nums) {
            int farIndex = 0, count = 0, best = 0;
            for (int idx = 0; idx < nums.length && farIndex < nums.length - 1; idx ++) {
                best = Math.max (best, idx + nums [idx]);
                if (farIndex == idx) { farIndex = best; count ++; best = 0; }
            }
            return count;
    }
    

  • 0
    S

    @wei31 Maybe there is no need to add if (currentMax == nextMax) return INT_MAX; when the inside for {} loop end, i ==
    currentMax+1
    , if currentMax == nextMax holds, then the outside while() loop condition will not hold anymore.
    Just modify return 0 to return INT_MAX will also work.


Log in to reply
 

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