Grokking 75:Jump Game II(medium)

Problem Statement

You are given an array nums containing n integers, where nums[i] represents the maximum length of a forward jump you can make from index i. You are initially positioned at nums[0].

Return the minimum number of jumps needed to reach from the start to the end of the array.

Examples

Example 1:

Input: nums = [2, 3, 2, 2, 1]
Expected Output: 2
Justification: Start at index 0 and jump to index 1 (jump size 1). Then, jump from index 1 to the end (jump size 3).

Example 2:

Input: nums = [1, 2, 3, 4, 5]
Expected Output: 3
Justification: Start at index 0, jump to index 1 (jump size 1). Then, jump to index 3 (jump size 2). Finally, jump to the end (jump size 2).

Example 3:

Input: nums = [2, 3, 1, 2, 4, 1]
Expected Output: 3
Justification: Start at index 0, jump to index 1 (jump size 1). Then, jump to index 4 (jump size 2). Finally, jump to the end (jump size 1).

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 1000
It’s guaranteed that you can reach nums[n – 1].

Solution

To solve this problem, we need to keep track of the farthest point we can reach with each jump and count how many jumps we need. The strategy is to iterate through the array while updating the farthest point we can reach. Whenever we reach the end of the current jump range, we increment our jump count and update the current jump range to the farthest point we can reach. This method ensures that we use the fewest jumps possible to get to the end.

This approach works effectively because it uses a greedy algorithm to always make the optimal choice at each step. By focusing on the farthest reachable point, we minimize the number of jumps needed.

Step-by-Step Algorithm

Initialize Variables:
- Create a variable jumps and set it to 0. This will count the number of jumps needed.
- Create a variable currentEnd and set it to 0. This will mark the end of the range for the current jump.
- Create a variable farthest and set it to 0. This will track the farthest point that can be reached.
Loop Through the Array:
- Iterate through the array from the first element to the second-to-last element (from index 0 to n-2):
  - Update farthest to be the maximum of farthest and the current index plus the jump length at that index (farthest = max(farthest, i + nums[i])).
  - If the current index is equal to currentEnd:
    - Increment the jumps count (jumps++).
    - Update currentEnd to be farthest (currentEnd = farthest).
Return Result:
- After the loop ends, return the value of jumps as the result.

Algorithm Walkthrough

Using the input nums = [2, 3, 1, 2, 4, 1].

Initialization:

jumps = 0
currentEnd = 0
farthest = 0

Iteration 1:

Index i = 0
- farthest = max(0, 0 + 2) = 2
- Since i == currentEnd (0 == 0):
  - jumps++ (jumps = 1)
  - currentEnd = farthest (currentEnd = 2)

Iteration 2:

Index i = 1
- farthest = max(2, 1 + 3) = 4
- i != currentEnd (1 != 2), so do nothing

Iteration 3:

Index i = 2
- farthest = max(4, 2 + 1) = 4
- Since i == currentEnd (2 == 2):
  - jumps++ (jumps = 2)
  - currentEnd = farthest (currentEnd = 4)

Iteration 4:

Index i = 3
- farthest = max(4, 3 + 2) = 5
- i != currentEnd (3 != 4), so do nothing

Iteration 5:

Index i = 4
- farthest = max(5, 4 + 4) = 8
- Since i == currentEnd (4 == 4):
  - jumps++ (jumps = 3)
  - currentEnd = farthest (currentEnd = 8)

Return Result:

Return jumps which is 3.

Code

public class Solution {
    public int jump(int[] nums) {
        int jumps = 0;  // To count the number of jumps
        int currentEnd = 0;  // To mark the end of the range for the current jump
        int farthest = 0;  // To mark the farthest point that can be reached

        // Loop through the array
        for (int i = 0; i &lt; nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);  // Update the farthest point
            if (i == currentEnd) {  // If reached the end of the current jump range
                jumps++;  // Increment jump count
                currentEnd = farthest;  // Update the end of the range to the farthest point
            }
        }

        return jumps;  // Return the number of jumps
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test examples
        int[] example1 = {2, 3, 2, 2, 1};
        int[] example2 = {1, 2, 3, 4, 5};
        int[] example3 = {2, 3, 1, 2, 4, 1};

        // Print the results
        System.out.println(solution.jump(example1)); // Expected Output: 2
        System.out.println(solution.jump(example2)); // Expected Output: 3
        System.out.println(solution.jump(example3)); // Expected Output: 3
    }
}

class Solution {
    jump(nums) {
        let jumps = 0;  // To count the number of jumps
        let currentEnd = 0;  // To mark the end of the range for the current jump
        let farthest = 0;  // To mark the farthest point that can be reached

        // Loop through the array
        for (let i = 0; i &lt; nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);  // Update the farthest point
            if (i === currentEnd) {  // If reached the end of the current jump range
                jumps++;  // Increment jump count
                currentEnd = farthest;  // Update the end of the range to the farthest point
            }
        }

        return jumps;  // Return the number of jumps
    }
}

// Test examples
const solution = new Solution();

const example1 = [2, 3, 2, 2, 1];
const example2 = [1, 2, 3, 4, 5];
const example3 = [2, 3, 1, 2, 4, 1];

// Print the results
console.log(solution.jump(example1)); // Expected Output: 2
console.log(solution.jump(example2)); // Expected Output: 3
console.log(solution.jump(example3)); // Expected Output: 3

Complexity Analysis

Time Complexity:O(n) The algorithm runs in time, where n is the length of the array. This is because we iterate through the array once, and each operation inside the loop (like updating the farthest point) takes constant time.
Space Complexity: O(1)The algorithm uses additional space since we are only using a few extra variables (jumps, currentEnd, and farthest) regardless of the input size.