💬 Discord
Sign In
NeetCode #780LC-55MediumGreedyBlind 75NC 150NC 250
← Back to All Problems

#780 · #55 · Jump Game(跳跃游戏)

📌 Problem Statement & Constraints

You are given an integer array nums and start at index 0. Each element nums[i] is the maximum jump length from that position. Return true if you can reach the last index, otherwise false. Constraints: 1 <= nums.length <= 10^4, 0 <= nums[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Greedily maintain reach, the furthest index reachable so far.
  2. Scan left to right; if the current index i is beyond reach, it is unreachable, so return false.
  3. Otherwise update reach = max(reach, i + nums[i]).
  4. The key insight is that a position is reachable iff some earlier reachable position can jump past it, so a single pass over reachable indices suffices.

💻 Benchmark Python3 Implementation

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reach = 0
        for i, x in enumerate(nums):
            if i > reach:              # a gap we cannot cross
                return False
            reach = max(reach, i + x)
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass; reach only grows.
💾 Space Complexity
O(1): a single scalar.

⚠️ Interview Pitfalls & Follow-ups

  • Checking i > reach after updating reach: the check must come first, otherwise an unreachable index would be treated as reachable.
  • Assuming you must land exactly on the last index: you only need to reach it; reach >= n - 1 is enough.
  • Stopping the loop early once reach >= n - 1: harmless optimisation, but forgetting that a zero at index 0 with n > 1 is an immediate false is the real bug.
  • Using DP or BFS: both are correct but O(n) space or worse; the greedy reach is sufficient.