Jump Game
LeetCode #55 · Medium · Greedy · C++ solution with worked-out approach and complexity analysis.
Approach
Greedy - Track Maximum Reachable Position
Key insight
We only need to track the farthest position we can reach. If at any point we can't move forward (stuck at 0 with maxPos <= current position), we can't reach the end.
Strategy
- 1Iterate through the array, tracking maxPos (farthest reachable index)
- 2At each position i, update maxPos = max(maxPos, i + nums[i])
- 3If maxPos reaches or exceeds the last index, return true
- 4If we encounter a 0 and can't jump past it (maxPos <= i), return false
- 5If we complete the loop, we can reach the end
Time
O(n)
single pass through the array
Space
O(1)
only using a few variables
Problem description(from LeetCode)
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.
Examples
Example 1
- Input:
- nums = [2,3,1,1,4]
- Output:
- true
- Note:
- Jump 1 step from index 0 to 1, then 3 steps to the last index. Input: nums = [3,2,1,0,4] Output: false Explanation: 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.
Constraints
- •1 <= nums.length <= 10^4
- •0 <= nums[i] <= 10^5
C++ Solution
solution.cpp
class Solution {
public:
bool canJump(vector<int> &nums) {
int maxPos = 0, n = nums.size();
for (int i = 0; i < n; i++) {
maxPos = max(maxPos, i + nums[i]);
if (maxPos >= n - 1) return true;
if (nums[i] == 0 && maxPos <= i) return false;
}
return true;
}
};