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.
1var canJump = function(nums) {
2 let maxReach = 0;
3 for (let i = 0; i < nums.length; i++) {
4 if (i > maxReach) return false;
5 maxReach = Math.max(maxReach, i + nums[i]);
6 if (maxReach >= nums.length - 1) return true;
7 }
8 return false;
9};This JavaScript solution utilizes a greedy technique that scans through each index and calculates how far it can jump to, updating maxReach. When the index i is unachievable, false is returned. True will be returned early if we can already reach or exceed the last index.
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.
1public class Solution {
2 public bool CanJump(int[] nums) {
3 bool[] dp = new bool[nums.Length];
4 dp[0] = true;
5 for (int i = 0; i < nums.Length; i++) {
6 if (dp[i]) {
7 for (int j = 1; j <= nums[i] && i + j < nums.Length; j++) {
8 dp[i + j] = true;
9 }
10 }
11 }
12 return dp[nums.Length - 1];
13 }
14}The C# version applies dynamic programming to set reachability for each index, mirroring other related solutions. The return value from evaluating the end of the array ultimately reflects truth via dp[nums.Length - 1].