• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
int jump(vector<int>& nums) {
int ans = 0;
int end = 0;
int farthest = 0;

// implicit BFS
for (int i = 0; i < nums.size() - 1; ++i) {
farthest = max(farthest, i + nums[i]);
if (farthest >= nums.size() - 1) {
++ans;
break;
}
if (i == end) {    // visited all the items on the current level
++ans;           // increment the level
end = farthest;  // make the queue size for the next level
}
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int jump(int[] nums) {
int ans = 0;
int end = 0;
int farthest = 0;

// implicit BFS
for (int i = 0; i < nums.length - 1; ++i) {
farthest = Math.max(farthest, i + nums[i]);
if (farthest >= nums.length - 1) {
++ans;
break;
}
if (i == end) {   // visited all the items on the current level
++ans;          // increment the level
end = farthest; // make the queue size for the next level
}
}

return ans;
}
}
``````

## Python

``````class Solution:
def jump(self, nums: List[int]) -> int:
ans = 0
end = 0
farthest = 0

# implicit BFS
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if farthest >= len(nums) - 1:
ans += 1
break
if i == end:      # visited all the items on the current level
ans += 1        # increment the level
end = farthest  # make the queue size for the next level

return ans
``````