Leetcode 45. Jump Game II
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 fromi
. - If
farthest
is greater than or equal to the last index, we incrementans
and break (because we can reach the last index from the current index). - If
i
reachesend
, it means we have visited all the items on the current level, so we incrementans
and setend
tofarthest
.
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
farthest
is updated to0 + 2 = 2
.- Now
i
equals toend
, soans
is incremented by 1 (from 0 to 1) andend
is updated tofarthest=2
. i
becomes1
, andfarthest
is updated tomax(2, 1 + 3) = 4
.- Now
i
moves to2
and3
. However, sincefarthest
has reached the last index, we incrementans
and break the loop. - 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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.