LeetCode Problem

Problem Description

Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.

Examples

Input: [2,3,1,1,4]
Output: 2

Input: [2,3,0,1,4]
Output: 2

Constraints

1 <= nums.length <= 10^4
0 <= nums[i] <= 1000

Follow-up

Approach to Solve

Use a greedy approach to find the minimum number of jumps.

Code Implementation

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0
        jumps = 0
        current_max = 0
        next_max = 0
        for i in range(n - 1):
            next_max = max(next_max, i + nums[i])
            if i == current_max:
                jumps += 1
                current_max = next_max
                if current_max >= n - 1:
                    break
        return jumps

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0;
        int jumps = 0;
        int currentMax = 0;
        int nextMax = 0;
        for (int i = 0; i < n - 1; i++) {
            nextMax = Math.max(nextMax, i + nums[i]);
            if (i == currentMax) {
                jumps++;
                currentMax = nextMax;
                if (currentMax >= n - 1) break;
            }
        }
        return jumps;
    }

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;
        int jumps = 0;
        int currentMax = 0;
        int nextMax = 0;
        for (int i = 0; i < n - 1; i++) {
            nextMax = max(nextMax, i + nums[i]);
            if (i == currentMax) {
                jumps++;
                currentMax = nextMax;
                if (currentMax >= n - 1) break;
            }
        }
        return jumps;
    }

Explanation

This solution uses a greedy approach to solve the problem. Here's a detailed explanation of the algorithm:

Initialize variables: jumps (number of jumps), currentMax (farthest reachable index in the current jump), and nextMax (farthest reachable index in the next jump).
Iterate through the array from left to right (except the last element):
- Update nextMax to be the maximum of its current value and i + nums[i].
- If we've reached the currentMax:
  - Increment jumps.
  - Update currentMax to nextMax.
  - If currentMax is greater than or equal to the last index, break the loop.
Return the number of jumps.

The time complexity is O(n) as we iterate through the array once, and the space complexity is O(1) as we only use a constant amount of extra space.

Complexity

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

LeetSolved

Jump Game II