NUHMAN.com

Introduction

LeetCode 55: Jump Game is a fundamental problem that teaches you how to evaluate reachability within an array. You're given an array where each element represents the maximum number of steps you can jump forward. The task is to determine whether you can reach the last index starting from the first index.

It’s a common interview problem and can be solved efficiently with a greedy approach.

Problem Statement

You are given an array of non-negative integers nums. Each element represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example:

go

Input: nums = [2, 3, 1, 1, 4]
Output: true
Explanation: You can jump to the last index as follows: 0 → 1 → 4

Counter Example:

go

Input: nums = [3, 2, 1, 0, 4]
Output: false
Explanation: You will get stuck at index 3 with no way to reach index 4.

Constraints

• 1 <= nums.length <= 10⁴
• 0 <= nums[i] <= 10⁵

Approach: Greedy Algorithm

The key idea is to always track the farthest index you can reach. At each step:

1. If the current index is beyond your max reach, return false.
2. Update the farthest reach.
3. If the farthest reach is greater than or equal to the last index, return true.

Go Implementation

go

func canJump(nums []int) bool {
    farthest := 0
    for i := 0; i <= farthest; i++ {
        farthest = max(farthest, i+nums[i])
        if farthest >= len(nums)-1 {
            return true
        }
    }
    return false
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Example Walkthrough

Given nums = [2, 3, 1, 1, 4]:

• Start at index 0: max reach = 0 + 2 = 2
• Index 1: max reach = max(2, 1 + 3) = 4
• Index 2: max reach = max(4, 2 + 1) = 4

Now farthest = 4, which is the last index. Return true.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Efficient single pass with constant space.

Edge Cases

• Single element array: Always true.
• All elements are zeros except the first: If first is big enough → true, else false.
• Large arrays with zero in the middle: Must check if it can be jumped over.

Alternative Approaches

• Dynamic Programming (Bottom-up or Top-down): Solves the problem but uses more space and time.
• BFS/DFS: Too slow for large inputs (TLE on LeetCode).

Key Takeaways

• Track the farthest reachable index at each step.
• Greedy approach avoids unnecessary computation.
• One of the most optimal solutions for this problem.