55. Jump Game
Explanation
To solve this problem, we can use a greedy approach. We iterate through the array from left to right, keeping track of the furthest index we can reach. At each index, we update the furthest index we can reach based on the current element's value and the furthest index we have seen so far. If at any point, the current index is greater than the furthest index we can reach, we return false as it means we cannot reach the end. If we successfully reach the end of the array, we return true.
- Time complexity: O(n), where n is the number of elements in the input array.
- Space complexity: O(1)
class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) {
return false;
}
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) {
return true;
}
}
return false;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.