{"id":958,"date":"2025-08-21T18:21:11","date_gmt":"2025-08-21T12:51:11","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=958"},"modified":"2025-08-21T18:21:13","modified_gmt":"2025-08-21T12:51:13","slug":"jump-game","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/jump-game\/","title":{"rendered":"Jump Game | Leetcode 55 | Greedy Solution"},"content":{"rendered":"\n

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

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.<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

\n\n\n\n

Problem Statement \u2013 What Does the Problem Say?<\/h2>\n\n\n\n

You are given an array nums<\/code> where each element nums[i]<\/code> represents the maximum jump length<\/strong> you can move forward from index i<\/code>.<\/p>\n\n\n\n

Starting at index 0, your task is to determine whether you can reach the last index<\/strong>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input: <\/span>nums<\/span> = [<\/span>2<\/span>,<\/span>3<\/span>,<\/span>1<\/span>,<\/span>1<\/span>,<\/span>4<\/span>]<\/span><\/span>\nOutput:<\/span> True<\/span><\/span>\nExplanation:<\/span><\/span>\n-<\/span> Start<\/span> at index <\/span>0<\/span> \u2192 you can jump at most <\/span>2<\/span> steps.<\/span><\/span>\n-<\/span> Jump<\/span> <\/span>to<\/span> index <\/span>1<\/span> \u2192 nums[<\/span>1<\/span>] = <\/span>3<\/span> allows reaching further indices.<\/span><\/span>\n-<\/span> From<\/span> index <\/span>1<\/span>,<\/span> you<\/span> can reach the last <\/span>index<\/span> (<\/span>4<\/span>).<\/span><\/span>\nSo,<\/span> the<\/span> answer is<\/span> True<\/span>.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input: <\/span>nums<\/span> = [<\/span>3<\/span>,<\/span>2<\/span>,<\/span>1<\/span>,<\/span>0<\/span>,<\/span>4<\/span>]<\/span><\/span>\nOutput:<\/span> False<\/span><\/span>\nExplanation:<\/span><\/span>\n-<\/span> Start<\/span> at index <\/span>0<\/span> \u2192 you can jump at most <\/span>3<\/span> steps.<\/span><\/span>\n-<\/span> You<\/span> can reach up <\/span>to<\/span> index <\/span>3<\/span>.<\/span><\/span>\n-<\/span> But<\/span> at index <\/span>3<\/span>,<\/span> nums<\/span>[<\/span>3<\/span>] = <\/span>0<\/span>,<\/span> so<\/span> you are stuck and cannot reach the last index.<\/span><\/span>\nSo,<\/span> the<\/span> answer is<\/span> False<\/span>.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
The challenge is to decide whether the last index can be reached while following the given jumping rules.<\/p>\n\n\n\n
\n\n\n\n
Intuition and Approach (Optimal \u2013 Greedy)<\/h2>\n\n\n\n
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<\/strong>.<\/p>\n\n\n\n
Why this works:<\/h3>\n\n\n\n