{"id":961,"date":"2025-08-21T18:28:53","date_gmt":"2025-08-21T12:58:53","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=961"},"modified":"2025-08-21T18:28:55","modified_gmt":"2025-08-21T12:58:55","slug":"jump-game-ii","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/","title":{"rendered":"Jump Game II | Leetcode 45 | Recursive and Greedy Solution"},"content":{"rendered":"\n<p>This problem asks: given an array <code>nums<\/code> where <code>nums[i]<\/code> is the maximum jump length from index <code>i<\/code>, find the <strong>minimum number of jumps<\/strong> needed to reach the last index. You start at index <code>0<\/code>. You can always assume the last index is reachable as per the original LeetCode statement.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/jump-game-ii\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-54ba7cd7-126c-406d-ad7f-3eff70486ce0\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#0-what-does-the-problem-say-with-examples\" style=\"\">What does the problem say? (with examples)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#1-solution-1-simple-recursion\" style=\"\">Solution 1: Simple Recursion<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#2-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#3-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#5-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#6-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#7-solution-2-greedy-optimal\" style=\"\">Solution 2: Greedy (Optimal)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#8-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#9-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#10-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#11-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#12-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/jump-game-ii\/#13-final-takeaway\" style=\"\">Final Takeaway<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"0-what-does-the-problem-say-with-examples\">What does the problem say? (with examples)<\/h2>\n\n\n\n<p>You need to reach the last index in the fewest jumps.<\/p>\n\n\n\n<p><strong>Example 1<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"Input: nums = [2,3,1,1,4]\nOutput: 2\nExplanation: Jump from index 0 -&gt; 1 (length 1), then 1 -&gt; 4 (length 3).\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">Input: <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\"> = [<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">,<\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">Output: <\/span><span style=\"color: #B5CEA8\">2<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">Explanation: Jump from index <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> -&gt; <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> (<\/span><span style=\"color: #9CDCFE\">length<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">),<\/span><span style=\"color: #9CDCFE\"> then<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> -&gt; <\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\"> (<\/span><span style=\"color: #9CDCFE\">length<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">).<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p><strong>Example 2<\/strong><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"Input: nums = [2,3,0,1,4]\nOutput: 2\nExplanation: 0 -&gt; 1, then 1 -&gt; 4.\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #DCDCAA\">Input<\/span><span style=\"color: #D4D4D4\">: nums = [2,3,0,1,4]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #DCDCAA\">Output<\/span><span style=\"color: #D4D4D4\">: 2<\/span><\/span>\n<span class=\"line\"><span style=\"color: #DCDCAA\">Explanation<\/span><span style=\"color: #D4D4D4\">: 0 -&gt; 1, then 1 -&gt; 4.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>Key insight: you are minimizing the number of jumps, not the distance per jump. Large jumps can be good if they reduce the number of total moves.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"1-solution-1-simple-recursion\">Solution 1: Simple Recursion<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<p>A straightforward idea is to try <strong>all possible jumps<\/strong> from the current index and choose the minimum among them. From <code>index<\/code>, you can jump up to <code>nums[index]<\/code> steps forward. Recursively compute the minimum jumps needed from each reachable next index and take the minimum.<\/p>\n\n\n\n<p>This is a direct search of the decision tree:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Base case: if <code>index<\/code> is at or beyond the last index, return the number of jumps taken so far.<\/li>\n\n\n\n<li>Otherwise, try every jump length from <code>1<\/code> to <code>nums[index]<\/code> and take the minimum of those results.<\/li>\n<\/ul>\n\n\n\n<p>This approach is correct but explores many overlapping subproblems without caching, which makes it very slow on large inputs.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, index, jump, lastIndex, nums):\n        if index &gt;= lastIndex:\n            return jump\n        minJump = float(&quot;inf&quot;)\n        for i in range(1, nums[index] + 1):\n            minJump = min(minJump, self.solve(index + i, jump + 1, lastIndex, nums))\n        return minJump\n\n    def jump(self, nums: List[int]) -&gt; int:\n        return self.solve(0, 0, len(nums) - 1, nums)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">index<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">jump<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">lastIndex<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> index &gt;= lastIndex:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> jump<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        minJump = <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, nums[index] + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            minJump = <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\">(minJump, <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(index + i, jump + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, lastIndex, nums))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> minJump<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">jump<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums) - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, nums)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>solve(index, jump, lastIndex, nums)<\/code> returns the minimal jumps to reach or pass <code>lastIndex<\/code> starting from <code>index<\/code>, given that you have already taken <code>jump<\/code> jumps.<\/li>\n\n\n\n<li>If <code>index >= lastIndex<\/code>, you are done and return <code>jump<\/code>.<\/li>\n\n\n\n<li>Otherwise, you iterate possible next steps <code>i<\/code> from <code>1<\/code> to <code>nums[index]<\/code>, recursively compute the answer for <code>index + i<\/code>, and track the minimum.<\/li>\n\n\n\n<li><code>jump(nums)<\/code> starts the process from index <code>0<\/code> with <code>0<\/code> jumps.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Precise:<\/strong> In the worst case, from each index you branch up to <code>nums[index]<\/code> times and recompute many subproblems repeatedly. This yields <strong>exponential time<\/strong>, commonly characterized as worse than <code>O(2^n)<\/code> for adversarial inputs.<\/li>\n\n\n\n<li><strong>Simplified:<\/strong> Exponential time. Not feasible for large arrays.<\/li>\n\n\n\n<li><strong>Space:<\/strong> The maximum recursion depth is at most <code>n<\/code>, so <strong>O(n)<\/strong> stack space.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-conclusion\">Conclusion<\/h3>\n\n\n\n<p>Simple recursion is easy to understand but impractical without memoization or other optimizations. It suffers from massive recomputation and will time out on typical test cases.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-solution-2-greedy-optimal\">Solution 2: Greedy (Optimal)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<p>A classic greedy strategy solves this in linear time by viewing the array as <strong>levels<\/strong> of reachable indices:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Maintain the current <strong>window<\/strong> <code>[left, right]<\/code> of indices you can reach with the current number of jumps.<\/li>\n\n\n\n<li>Within this window, compute the <strong>farthest<\/strong> index you can reach with one more jump.<\/li>\n\n\n\n<li>Move to the next window and increment the jump count.<\/li>\n\n\n\n<li>Repeat until the right boundary reaches or passes the last index.<\/li>\n<\/ul>\n\n\n\n<p>This is analogous to a breadth-first expansion across indices, but implemented with two pointers and a single pass.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def jump(self, nums: List[int]) -&gt; int:\n        n = len(nums)\n        jumps = 0\n        left = 0\n        right = 0\n        while right &lt; n - 1:\n            farthest = 0\n            for i in range(left, right + 1):\n                farthest = max(farthest, i + nums[i])\n            left = right + 1\n            right = farthest\n            jumps += 1\n        return jumps\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">jump<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        jumps = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        left = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        right = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> right &lt; n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            farthest = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(left, right + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                farthest = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(farthest, i + nums[i])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            left = right + <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            right = farthest<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            jumps += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> jumps<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>left<\/code> and <code>right<\/code> define the current range of indices reachable with <code>jumps<\/code> jumps.<\/li>\n\n\n\n<li>For every index <code>i<\/code> in the current range, compute how far you can go next as <code>i + nums[i]<\/code>, and track the maximum as <code>farthest<\/code>.<\/li>\n\n\n\n<li>After scanning the range, set the next range to <code>[right + 1, farthest]<\/code> and increment <code>jumps<\/code>.<\/li>\n\n\n\n<li>The loop stops when <code>right<\/code> has reached or crossed the last index. The counter <code>jumps<\/code> is the minimal number of jumps.<\/li>\n<\/ul>\n\n\n\n<p>This works because scanning all indices in the current reachable window ensures you consider every possible jump of length <code>jumps + 1<\/code> and choose the furthest frontier for the next step, which minimizes the total number of jumps.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Precise:<\/strong> Each index enters the inner loop exactly once across all iterations, so the total cost is <code>O(n)<\/code> for the scans plus <code>O(n)<\/code> for boundary updates, which is <strong>O(n + n)<\/strong>.<\/li>\n\n\n\n<li><strong>Simplified:<\/strong> <strong>O(n)<\/strong> time.<\/li>\n\n\n\n<li><strong>Space:<\/strong> Only a few variables are used, so <strong>O(1)<\/strong> extra space.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-conclusion\">Conclusion<\/h3>\n\n\n\n<p>The greedy window expansion is the optimal approach. It runs in linear time, uses constant space, and reliably computes the minimal number of jumps by expanding the furthest reachable frontier at each step.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"13-final-takeaway\">Final Takeaway<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Simple recursion explores all choices and is correct but exponential in time.<\/li>\n\n\n\n<li>The greedy window method is optimal, achieving <strong>O(n)<\/strong> time and <strong>O(1)<\/strong> space by expanding the reachable range level by level and counting how many expansions are needed.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>This problem asks: given an array nums where nums[i] is the maximum jump length from index i, find the minimum number of jumps needed to reach the last index. You start at index 0. You can always assume the last index is reachable as per the original LeetCode statement. Here&#8217;s the [Problem Link] to begin<\/p>\n","protected":false},"author":1,"featured_media":962,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[41,19],"class_list":{"0":"post-961","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-greedy-algorithm","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/08\/jump-game-II-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/961","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=961"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/961\/revisions"}],"predecessor-version":[{"id":963,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/961\/revisions\/963"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/962"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=961"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=961"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=961"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}