Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.
Example 1:
Input: [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: [3,2,1,0,4]
Output: falseExplanation: 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.
Simulation
You can simulate the jumping using recursion easily, however, this approach does not give you a ACCEPTED code, in fact, it will give you a Time Limit Exceeded error when input test cases are complex.
The idea is to jump as far as you can. If you can reach the end, then immediately return true, otherwise, when all possibilities are tested, it returns false. The recursion is time consuming and not very efficient. But this is another way of looking at this problem.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: bool jump(int A[], int p, int n) { if (p == n - 1) return true; // reaching the end for (int i = p + 1; i <= p + A[p]; i ++) { if (jump(A, i, n)) return true; // we can jump to the end. } return false; } bool canJump(int A[], int n) { return jump(A, 0, n); // jump from the beginning } }; |
class Solution { public: bool jump(int A[], int p, int n) { if (p == n - 1) return true; // reaching the end for (int i = p + 1; i <= p + A[p]; i ++) { if (jump(A, i, n)) return true; // we can jump to the end. } return false; } bool canJump(int A[], int n) { return jump(A, 0, n); // jump from the beginning } };
Greedy Algorithm
The O(n) solution is similar. We use a variable to record the maximum we can reach. And, we update the current position and this max-reach variable every time. At the end, we check if we are reaching the end.
1 2 3 4 5 6 7 8 9 | class Solution { public: bool canJump(int A[], int n) { int i = 0; // current position for (int reach = 0; i < n && i <= reach; ++i) reach = max(i + A[i], reach); // update max reach return i == n; } }; |
class Solution { public: bool canJump(int A[], int n) { int i = 0; // current position for (int reach = 0; i < n && i <= reach; ++i) reach = max(i + A[i], reach); // update max reach return i == n; } };
The Greedy algorithm can also be written slightly differently:
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution { public: bool canJump(vector<int>& nums) { int best = 0, cur = 0; for (int i = 0; i < nums.size(); ++ i) { best = max(best, i + nums[i]); if (cur == i) { cur = best; } } return cur >= nums.size() - 1; } }; |
class Solution { public: bool canJump(vector<int>& nums) { int best = 0, cur = 0; for (int i = 0; i < nums.size(); ++ i) { best = max(best, i + nums[i]); if (cur == i) { cur = best; } } return cur >= nums.size() - 1; } };
You see, how simple this is. Less is more!
Featured Comments
Very nice excercise(took me like 10 minutes to solve using recursion xD) however i’m kinda confused because in recursive solution they used >= last index but in non recursive solution they used == last index so it’s kinda confusing if reaching the end is reaching exactly last index or also over last index.
See also other variants of jump game solutions/algorithms:
- Teaching Kids Programming – Solving the Jump Game by Depth First Search Algorithm
- Teaching Kids Programming – Revisit Breadth First Search Algorithm via a Jumping Game
- Teaching Kids Programming – One-way Jump Game via Backtracking, DP and Greedy Algorithm
- Greedy Algorithm to Reach the Last Index of the Array
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Suppress Ads when WordPress Users are Logged in?
Next Post: Performance Testing the HDD/SSD/NVme Hard Disk speed on VPS/Dedicated Server