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.
1public class Solution {
2 public bool CanJump(int[] nums) {
3 int maxReach = 0;
4 for (int i = 0; i < nums.Length; i++) {
5 if (i > maxReach) return false;
6 maxReach = Math.Max(maxReach, i + nums[i]);
7 if (maxReach >= nums.Length - 1) return true;
8 }
9 return false;
10 }
11}The C# version uses a for-loop to traverse the array, managing maxReach to represent the furthest index available to step onto. If the loop counter i overtakes maxReach, false is returned. And if maxReach meets or exceeds the index of the last element, it returns 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.