Problem Explanation

Given an array of integers nums where each item represents the maximum jump length at that position. We are initially placed at the first position.

The goal is to reach the last index in the minimum number of jumps. You can assume that you can always reach the last index.

Example:

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

Output: 2

Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Approach

The problem can be solved by using the "Greedy Algorithm" approach.

We initialize end and farthest to 0, and ans to 0, where end is the current possible farthest point we could reach, farthest is the farthest point that we can reach from i, and ans is the minimum number of jumps.

We iterate the array from the beginning to the end.

• At each position, we update farthest with the furthest point we can reach from i.
• If farthest is greater than or equal to the last index, we increment ans and break (because we can reach the last index from the current index).
• If i reaches end, it means we have visited all the items on the current level, so we increment ans and set end to farthest.

Finally, we return ans as the result. This approach ensures we make the minimum number of jumps to reach the last index.

Let's walk through this with a simple example.

We start from this state:

1
2
3nums = [2,3,1,1,4]
4index:   0 1 2 3 4
5                  <--- goal

1. farthest is updated to 0 + 2 = 2.
2. Now i equals to end, so ans is incremented by 1 (from 0 to 1) and end is updated to farthest=2.
3. i becomes 1, and farthest is updated to max(2, 1 + 3) = 4.
4. Now i moves to 2 and 3. However, since farthest has reached the last index, we increment ans and break the loop.
5. Finally, we return ans=2 as the result.

Python Solution

1
2python
3class Solution:
4    def jump(self, nums):
5        ans = 0
6        end = 0
7        farthest = 0
8        # Implicit BFS
9        for i in range(len(nums) - 1):
10            farthest = max(farthest, i + nums[i])
11            if farthest >= len(nums) - 1:
12                ans += 1
13                break
14            if i == end:    # Visited all the items on the current level
15                ans += 1    # Increment the level
16                end = farthest  # Make the queue size for the next level
17        return ans

It's important to note that this greedy approach guarantees the optimal solution because we always make the jump to the farthest reachable point, which minimizes the number of jumps.

Java Solution

1
2java
3class Solution {
4    public int jump(int[] nums) {
5        int ans = 0;
6        int end = 0;
7        int farthest = 0;
8        for (int i = 0; i < nums.length - 1; i++) {
9            farthest = Math.max(farthest, i + nums[i]);
10            if (farthest >= nums.length - 1) {
11                ans++;
12                break;
13            }
14            if (i == end) {
15                ans++;
16                end = farthest;
17            }
18        }
19        return ans;
20    }
21}

JavaScript Solution

1
2javascript
3var jump = function(nums) {
4    let ans = 0;
5    let end = 0;
6    let farthest = 0;
7    for (let i = 0; i < nums.length - 1; i++) {
8        farthest = Math.max(farthest, i + nums[i]);
9        if (farthest >= nums.length - 1) {
10            ans++;
11            break;
12        }
13        if (i === end) {
14            ans++;
15            end = farthest;
16        }
17    }
18    return ans;
19};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int jump(vector<int>& nums) {
6        int ans = 0;
7        int end = 0;
8        int farthest = 0;
9        for (int i = 0; i < nums.size() - 1; i++) {
10            farthest = max(farthest, i + nums[i]);
11            if (farthest >= nums.size() - 1) {
12                ans++;
13                break;
14            }
15            if (i == end) {
16                ans++;
17                end = farthest;
18            }
19        }
20        return ans;
21    }
22};

C# Solution

1
2csharp
3public class Solution {
4    public int Jump(int[] nums) {
5       int ans = 0;
6        int end = 0;
7        int farthest = 0;
8        for (int i = 0; i < nums.Length - 1; i++) {
9            farthest = Math.Max(farthest, i + nums[i]);
10            if (farthest >= nums.Length - 1) {
11                ans++;
12                break;
13            }
14            if (i == end) {
15                ans++;
16                end = farthest;
17            }
18        }
19        return ans;
20    }
21}

In conclusion, this Greedy Algorithm approach is the best way to solve this problem, as it minimizes the number of jumps made to reach the last index. It does this by always jumping to the farthest reachable point. This algorithm is efficient as it only requires a single pass through the input array, resulting in linear time complexity (O(n)). It also doesn't require any extra space, leading to constant space complexity (O(1)). The solutions provided above, written in Python, Java, JavaScript, C++ and C#, all utilize this same approach, showing that it is widely applicable across multiple programming languages.