Description:
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Examples:
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.Solution in Python:
Python
from typing import List
class Solution:
def canJump(self, nums: List[int]) -> bool:
# Initialize the maximum reachable index to 0
max_reachable = 0
# Loop through each index and its value in the nums array
for i, jump in enumerate(nums):
# If the current index is greater than the maximum reachable index, return False
if i > max_reachable:
return False
# Update the maximum reachable index if the current index + jump is greater
max_reachable = max(max_reachable, i + jump)
# If the maximum reachable index is greater than or equal to the last index, return True
if max_reachable >= len(nums) - 1:
return True
# If we finish the loop without reaching the last index, return False
return FalseExplanation:
- Initialization:
max_reachableis initialized to 0. This variable keeps track of the farthest index that can be reached from the starting index.
- Loop Through the Array:
- We use a
forloop to iterate through each indexiand its corresponding jump lengthjumpin the arraynums.
- We use a
- Check If Current Index is Reachable:
- If the current index
iis greater thanmax_reachable, it means we cannot reach this index, so we returnFalse.
- If the current index
- Update Maximum Reachable Index:
- Update
max_reachableto be the maximum of its current value andi + jump. This accounts for the maximum index we can reach from the current indexi.
- Update
- Check If We Can Reach the Last Index:
- If
max_reachableis greater than or equal tolen(nums) - 1, it means we can reach the last index, so we returnTrue.
- If
- Return False If Loop Completes Without Reaching Last Index:
- If the loop completes and we haven’t returned
True, it means we cannot reach the last index, so we returnFalse.
- If the loop completes and we haven’t returned
This approach ensures that we efficiently check if we can reach the last index in a single pass through the array, making it an O(n) time complexity solution.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
// Initialize the maximum reachable index to 0
let maxReachable = 0;
// Loop through each index and its value in the nums array
for (let i = 0; i < nums.length; i++) {
// If the current index is greater than the maximum reachable index, return false
if (i > maxReachable) {
return false;
}
// Update the maximum reachable index if the current index + jump is greater
maxReachable = Math.max(maxReachable, i + nums[i]);
// If the maximum reachable index is greater than or equal to the last index, return true
if (maxReachable >= nums.length - 1) {
return true;
}
}
// If we finish the loop without reaching the last index, return false
return false;
};Solution in Java:
Java
class Solution {
public boolean canJump(int[] nums) {
// Initialize the maximum reachable index to 0
int maxReachable = 0;
// Loop through each index in the nums array
for (int i = 0; i < nums.length; i++) {
// If the current index is greater than the maximum reachable index, return false
if (i > maxReachable) {
return false;
}
// Update the maximum reachable index if the current index + jump is greater
maxReachable = Math.max(maxReachable, i + nums[i]);
// If the maximum reachable index is greater than or equal to the last index, return true
if (maxReachable >= nums.length - 1) {
return true;
}
}
// If we finish the loop without reaching the last index, return false
return false;
}
}Solution in C#:
C#
public class Solution {
public bool CanJump(int[] nums) {
// Initialize the maximum reachable index to 0
int maxReachable = 0;
// Loop through each index in the nums array
for (int i = 0; i < nums.Length; i++) {
// If the current index is greater than the maximum reachable index, return false
if (i > maxReachable) {
return false;
}
// Update the maximum reachable index if the current index + jump is greater
maxReachable = Math.Max(maxReachable, i + nums[i]);
// If the maximum reachable index is greater than or equal to the last index, return true
if (maxReachable >= nums.Length - 1) {
return true;
}
}
// If we finish the loop without reaching the last index, return false
return false;
}
}