This approach involves maintaining a variable maxReach that stores the farthest index we can reach. We iterate through each index of the array and update maxReach. If at any index i, i is greater than maxReach, it means we cannot proceed further and thus return false. If we can iterate through the array successfully, return true.
Time Complexity: O(n), where n is the number of elements in the array. We make a single pass through the array.
Space Complexity: O(1), as we use only constant extra space.
1#include <stdbool.h>
2
3bool canJump(int* nums, int numsSize) {
4 int maxReach = 0;
5 for (int i = 0; i < numsSize; i++) {
6 if (i > maxReach) return false;
7 if (i + nums[i] > maxReach) maxReach = i + nums[i];
8 if (maxReach >= numsSize - 1) return true;
9 }
10 return false;
11}In this C solution, we iterate over the array and update the maxReach variable, which tracks the furthest index we can reach. If at any point the current index is greater than maxReach, we return false because it means we are stuck. If we are able to iterate through the entire array, it means we can reach the last index, so we return true.
This approach uses a Dynamic Programming (DP) table to track whether you can reach each index. Initialize a boolean array dp of the same length as nums, set all elements to false except the first (set to true since you're already at the start). Iterate through the array, and for each index marked true, update reachable indices as true using the jump capability at that index. Finally, return the boolean value of the last index.
Time Complexity: O(n^2), due to potential nested loop invocations over n indices.
Space Complexity: O(n), for the DP array storing reachable status for elements.
1class Solution:
2 def canJump(self, nums: List[int]) -> bool:
3 dp = [False] * len(nums)
4 dp[0] = True
5 for i in range(len(nums)):
6 if dp[i]:
7 for j in range(1, nums[i] + 1):
8 if i + j < len(nums):
9 dp[i + j] = True
10 return dp[-1]For the Python Dynamic Programming approach, prepare and examine an equivalent dp list, marking reachable indices using nested loops. The solution's final conclusion stands with the last position's value, dp[-1], whether reachable or not.