Jump Game | Leetcode 55 | Greedy Solution

The Jump Game is a popular interview problem and a classic example of applying a Greedy Algorithm. It appears frequently in coding tests and competitive programming because it tests both logical reasoning and the ability to optimize efficiently.

In this blog, we will carefully understand the problem, build the intuition for solving it, and then walk through the optimal Python implementation with explanation and complexity analysis.

Here’s the [Problem Link] to begin with.

Problem Statement – What Does the Problem Say?

You are given an array nums where each element nums[i] represents the maximum jump length you can move forward from index i.

Starting at index 0, your task is to determine whether you can reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: True
Explanation:
- Start at index 0 → you can jump at most 2 steps.
- Jump to index 1 → nums[1] = 3 allows reaching further indices.
- From index 1, you can reach the last index (4).
So, the answer is True.

Example 2:

Input: nums = [3,2,1,0,4]
Output: False
Explanation:
- Start at index 0 → you can jump at most 3 steps.
- You can reach up to index 3.
- But at index 3, nums[3] = 0, so you are stuck and cannot reach the last index.
So, the answer is False.

The challenge is to decide whether the last index can be reached while following the given jumping rules.

Intuition and Approach (Optimal – Greedy)

The greedy approach is the most efficient way to solve this problem. The key idea is to keep track of the farthest index you can reach at every step.

Why this works:

• If at any index i you are beyond the farthest index you can reach, it means you are stuck → return False.
• Otherwise, update the farthest reachable index as max(max_index, i + nums[i]).
• If you make it through the entire array, then the last index is reachable.

Steps to Solve:

1. Initialize max_index = 0, which keeps track of the farthest position you can reach.
2. Iterate through the array:
   • If i > max_index, it means you cannot even reach index i. Return False.
   • Otherwise, update max_index = max(max_index, i + nums[i]).
3. If the loop finishes successfully, return True.

This greedy choice ensures that you always know the maximum range you can reach at every point.

Code Implementation

Here’s the Python code for the Jump Game problem using the greedy method (with added comments for clarity):

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_index = 0  # farthest index we can reach

        for i in range(len(nums)):
            if i > max_index:
                # if we are at an index we cannot reach
                return False
            # update the farthest index reachable
            max_index = max(max_index, i + nums[i])

        return True

Code Explanation

• Start with max_index = 0, meaning at the beginning you can only stay at index 0.
• For each index i, check:
  • If i is greater than max_index, it means you are stuck because you cannot even reach i.
  • Otherwise, extend the farthest reachable index using i + nums[i].
• By the time the loop ends, if you have not returned False, it means you can reach the last index.

For example:

• nums = [2,3,1,1,4]
  • Start with max_index = 0.
  • At index 0, update max_index = max(0, 0+2) = 2.
  • At index 1, update max_index = max(2, 1+3) = 4.
  • At index 2, max_index remains 4.
  • At index 3, max_index remains 4.
  • At index 4, loop ends → reachable. Return True.

Time and Space Complexity

• Time Complexity:
  • We go through the array once.
  • O(n) where n = length of the array.
• Space Complexity:
  • We only use one variable max_index.
  • O(1) constant extra space.

This makes the solution optimal and efficient.

Conclusion

The Jump Game problem is a great demonstration of how Greedy Algorithms simplify complex problems. By keeping track of the farthest reachable index, we can solve the problem in O(n) time and O(1) space.

This approach is both clean and efficient, making it the ideal solution for interviews and competitive programming.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.