Neetcode - Jump Game

Write code like you're telling a story—clear, intentional, and built to be understood.

This problem is relatively straightforward. The main idea is to check whether there exists a path that reaches the end of the array—or goes beyond it.

To better understand this, my initial approach was to visualize the possible moves as a tree structure. For example, take the input [2, 3, 0, 0]:

Index 0 (value = 2)
├── Index 1 (value = 3)
│ ├── Index 2 (value = 0)
│ └── Index 3 (value = 0)
└── Index 2 (value = 0)

You can observe that for each index, we have up to nums[index] options to move forward. Therefore, the key idea is to check whether there exists any path that can eventually reach the end of the array—specifically, index nums.size() - 1.

class Solution {
public:
  bool canJump(std::vector<int> &nums) {
    std::vector<int> memo(nums.size(), -1);

    return dfs(0, nums, memo);
  }

  bool dfs(int index, std::vector<int> &nums, std::vector<int> &memo) {
    if (index >= nums.size() - 1)
      return true;
    if (memo[index] != -1)
      return memo[index];

    int maxJump = std::min((int)nums.size() - 1, index + nums[index]);

    for (int next = index + 1; next <= maxJump; ++next) {
      if (dfs(next, nums, memo)) {
        memo[index] = 1;
        return true;
      }
    }

    return false;
  }
};

However, this is likely to face Time Limited Error (TLE) at competition. Therefore, it still better to use Greedy Method here. See below:

class Solution {
public: 
  bool canJump(vector<int>& nums) {
    int maxReach = 0;

    for (int i = 0; i < nums.size(); ++i) {
      if (i > maxReach) return false;

      maxReach = max(maxReach, i + nums[i]);
      if (maxReach >= nums.size() - 1) return true;
    }

    return false;
  }
}

I’d say the Greedy Method is more than just a simple trick—it’s a technical strategy. It requires uncovering the underlying mathematical relationships and understanding the problem at a more abstract level.

This kind of problem acts as a gateway, preparing us to tackle more complex challenges in the future. One important takeaway is learning to assess whether the current information is sufficient to make a reasonably good decision.

Conclusion

Short post today—no need for a long article every single day, right? 😅
I’m just a bit tired, haha.

Still, I think this question is worth a shot. It really helps sharpen critical thinking, especially from a recursion perspective. What I tried to do was approach it using an m-ary tree to explore the paths.

Anyway, wishing you a chill night. Good night!