Solution For Jump Game
Problem Statement:
You are given an array of non-negative integers nums
, where each element represents your maximum jump distance at that position. Your 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: nums = [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.
Solution:
The problem is to find the minimum number of jumps required to reach the last index. We can solve this problem using the greedy approach
- Initialize the variables: currEnd=0, currFarthest=0, and the number of jumps=0
- Iterate through the array from the first element to the last element
- For each element in the array:
a. Update the currFarthest to max(currFarthest, nums[i]+i)
b. If i == currEnd, update currEnd=currFarthest and increment the number of jumps by 1 - Return the number of jumps.
Dry Run:
Let’s dry run the above approach with the given example
nums = [2,3,1,1,4]
currEnd = currFarthest = jumps = 0
Iteration 1: nums[0]=2
currFarthest = max(0+2,0) = 2
Iteration 2: nums[1]=3
currFarthest = max(2+3,2) = 5
Iteration 3: nums[2]=1
currFarthest = max(5+1,3) = 6
Iteration 4: nums[3]=1
currFarthest = max(6+1,4) = 7
currEnd = 3, jumps=1
Iteration 5: nums[4]=4
currFarthest = max(7+4,5) = 11
currEnd = 7, jumps=2
Final value of jumps = 2
Time complexity: O(n)
Code:
def jump(nums):
currEnd = currFarthest = jumps = 0
for i in range(len(nums)-1):
currFarthest = max(currFarthest, i + nums[i])
if i == currEnd:
jumps += 1
currEnd = currFarthest
return jumps
Step by Step Implementation For Jump Game
class Solution { public boolean canJump(int[] nums) { //Greedy approach //Keep track of the furthest distance that can be reached //Starting from the first index, iterate through the array and update the furthest distance that can be reached //If the current index is greater than the furthest distance that can be reached, return false //Otherwise, return true int furthest = 0; for(int i=0; ifurthest) { return false; } furthest = Math.max(furthest, nums[i]+i); } return true; } }
class Solution: def canJump(self, nums: List[int]) -> bool: # keep track of the furthest index we can reach max_index = 0 # iterate through the array for i, num in enumerate(nums): # if the current index is greater than the furthest index we can reach, return False if i > max_index: return False # update max_index to be the greater of the two values (the current value or the current index + the value at the current index) max_index = max(max_index, i + num) # return True if we can reach the end of the array return True
var canJump = function(nums) { // Set up a variable to keep track of the furthest we can jump let max = 0; // Iterate through the array for (let i = 0; i < nums.length; i++) { // If the current index is greater than the furthest we can jump, return false if (i > max) { return false; } // Update max to be the furthest we can jump from the current index max = Math.max(i + nums[i], max); } // If we reach the end, return true return true; };
class Solution { public: bool canJump(vector& nums) { int n = nums.size(); int reach = 0; for (int i = 0; i < n; ++i) { if (i > reach || reach >= n - 1) break; reach = max(reach, i + nums[i]); } return reach >= n - 1; } };
public class Solution { public bool CanJump(int[] nums) { // keep track of the furthest index that can be reached int maxReach = 0; // iterate through the array for (int i = 0; i < nums.Length; i++) { // if the current index can't be reached, return false if (i > maxReach) { return false; } // update the furthest index that can be reached maxReach = Math.Max(maxReach, i + nums[i]); } // if the loop finishes, then all indices are reachable, so return true return true; } }