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 <vector>
2using namespace std;
3
4class Solution {
5public:
6 bool canJump(vector<int>& nums) {
7 int maxReach = 0;
8 for (int i = 0; i < nums.size(); i++) {
9 if (i > maxReach) return false;
10 maxReach = max(maxReach, i + nums[i]);
11 if (maxReach >= nums.size() - 1) return true;
12 }
13 return false;
14 }
15};In this C++ solution, we utilize a greedy strategy similar to the C implementation. We maintain the variable maxReach and iterate through the list of indices. We update maxReach to be the maximum of its current value or the sum of the current index and its jump capability. If the maxReach ever becomes greater than or equal to the last index, we can reach the last index, so we return true. If i surpasses maxReach, it implies we are stuck and return false.
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].