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

leetcode

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 exceeds maxReach, 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

Popular Posts