How I Solved the Jump Game Problem (LeetCode #55)

A beginner-friendly explanation using a greedy approach that beats 100% of C++ solutions.
π Problem Statement (Simplified)
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.
Example:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
π§ Thought Process
At every index, I need to decide how far I can go. My strategy is to keep track of the farthest index I can reach, and if at any point my current index exceeds that, I know I can't proceed further.
This makes it a classic greedy approach β always looking to stretch our reach as far as possible at each step.
βοΈ C++ Solution (Greedy Approach)
// Beats 100% C++ submissions
bool canJump(vector<int>& nums) {
int maxReach = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > maxReach) return false; // Can't reach this position
maxReach = max(maxReach, i + nums[i]); // Update farthest reach
}
return true; // If loop ends, we can reach the last index
}
π Explanation:
maxReach
keeps track of the furthest index we can reach.- If our current index
i
ever exceedsmaxReach
, it means there's a gap we canβt jump over. - Otherwise, we keep updating
maxReach
to see how far we can go.
π§ͺ Dry Run Example
nums = [3, 2, 1, 0, 4]
- i = 0 β maxReach = 3
- i = 1 β maxReach = 3
- i = 2 β maxReach = 3
- i = 3 β maxReach = 3
- i = 4 β 4 > 3 β β return false
So the function correctly returns false
when the end is unreachable.
π What I Learned
- This problem taught me how powerful greedy algorithms can be for problems with optimal substructure.
- I also learned to simulate the problem on paper before jumping into code.
- LeetCode editorials and community solutions helped me validate and refine my logic.
π Related Resources
π¬ Final Thoughts
Even small algorithm problems like this one can teach valuable lessons about problem-solving strategies. If you're a beginner, try not just solving problems β explain your thought process. Thatβs where real learning happens.
I'll be sharing more beginner-friendly explanations in the coming weeks. Stay tuned!
Comments
Post a Comment