# O(n), BFS solution

• 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;
}``````

(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;
}
}``````

• 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``````

• 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.

• 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!

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

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

• 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;
}``````

• while condition could be written as

``````while(i <= currentMax)
``````

This is more concise and easier to understand

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

• @tju_xu97 Can you explain your code?

• 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;
}
};

• 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;
}
``````

• This post is deleted!

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

• 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;
}
``````

• @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.

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