{"id":2859,"date":"2021-10-25T12:17:34","date_gmt":"2021-10-25T06:47:34","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2859"},"modified":"2022-06-15T11:50:53","modified_gmt":"2022-06-15T06:20:53","slug":"minimum-number-of-jumps","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/minimum-number-of-jumps\/","title":{"rendered":"Minimum Number of Jumps"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#minimum-jumps-to-reach-end-of-an-array\">Minimum Jumps To Reach End of an Array<\/a><\/li><li><a href=\"#approach-1-bruteforcerecursive\">Approach 1: Bruteforce(Recursive)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c--implementation\">C++ <meta charset=\"utf-8\">Implementation<\/a><\/li><li><a href=\"#java--implementation\">Java <meta charset=\"utf-8\">Implementation<\/a><\/li><li><a href=\"#python--implementation\">Python <meta charset=\"utf-8\">Implementation<\/a><\/li><\/ul><li><a href=\"#approach-2-dynamic-programming\">Approach 2: Dynamic Programming<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c--code-for-dp-method\">C++ <meta charset=\"utf-8\">Code For DP Method<\/a><\/li><li><a href=\"#java-code-for-dp-method\">Java Code For DP Method<\/a><\/li><li><a href=\"#python-code-for-dp-method-\">Python Code For DP Method <\/a><\/li><\/ul><li><a href=\"#approach-3-greedy-approach\">Approach 3: Greedy Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c--code-for-greedy-approach\">C++ <meta charset=\"utf-8\">Code For Greedy Approach<\/a><\/li><li><a href=\"#java--code-for-greedy-approach\">Java <meta charset=\"utf-8\">Code For Greedy Approach<\/a><\/li><li><a href=\"#python-code-for-greedy-approach\">Python Code For Greedy Approach<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faq\">FAQ<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"minimum-jumps-to-reach-end-of-an-array\">Minimum Jumps To Reach End of an Array<\/h2>\n\n\n\n<p>Given an array of non-negative integers, <strong>A<\/strong>, of length <strong>N<\/strong>. You are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position.<\/p>\n\n\n\n<p>Return the minimum number of jumps required to reach the last index.<\/p>\n\n\n\n<p>If it is not possible to reach the last index, return <strong>-1<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"837\"  height=\"310\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Minimum Jumps \"  class=\"wp-image-3185 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 837px) 100vw, 837px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/minimum-jumps.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/minimum-jumps.png 837w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/minimum-jumps-300x111.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/minimum-jumps-768x284.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/minimum-jumps-380x141.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/minimum-jumps-550x204.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/minimum-jumps-800x296.png 800w\" ><\/figure>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>arr[] = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]<br><strong>Output: <\/strong>3<br><strong>Explanation: <\/strong>Provided in the above image<\/p>\n\n\n\n<p><strong>Input: <\/strong>&nbsp;arr[] = [2, 3, 1, 1, 4]<br><strong>Output:<\/strong> 2<br><strong>Explanation:<\/strong> Travel from 2 -&gt; 3 -&gt; end.<\/p>\n\n\n\n<h2 id=\"approach-1-bruteforcerecursive\">Approach 1: Bruteforce(Recursive)<\/h2>\n\n\n\n<p>A simple approach to solve this problem is to start from the first element of the array and recursively travel to all elements that are reachable from that element. Similarly, recursively travel to all other elements and find the minimum jumps to reach the end of the array.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"824\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Bruteforce\"  class=\"wp-image-3186 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce-1024x824.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce-1024x824.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce-300x241.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce-768x618.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce-1536x1236.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce-2048x1648.png 2048w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce-380x306.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce-550x443.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce-800x644.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce-1160x934.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Bruteforce.png 2915w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Create a recursive function that determines the minimum jumps required to reach the end of the array.<\/li><li>Start from the first element of the array and recurse for each step till current step &gt; 0.<\/li><li>Minimise the value for each iteration.<\/li><li>Return the minimum jumps.<\/li><\/ul>\n\n\n\n<h3 id=\"c--implementation\"><span id=\"c-implementation\">C++ <meta charset=\"utf-8\">Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> \nint decideJump(int nums[], int n, int currPos){\n    if(currPos >=  n-1){\n        return 0;\n    }\n    int minJump = INT_MAX;\n    int maxSteps = nums[currPos]\n    while(maxSteps > 0){\n        minJump = min(minJump, 1 + decideJump(nums,n,currPos+maxSteps))\n        maxSteps = maxSteps - 1;\n    }\n    return minJump\n}\n   \nint jump(int nums[], int n) {\n    return decideJump(nums, n, 0);\n}<\/pre>\n\n\n\n<h3 id=\"java--implementation\"><span id=\"java-implementation\">Java <meta charset=\"utf-8\">Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int decideJump(int[] nums, int n, int currPos){\n    if(currPos >=  n-1){\n        return 0\n    }\n    int minJump = INT_MAX\n    int maxSteps = nums[currPos]\n    while(maxSteps > 0){\n        minJump = min(minJump, 1 + decideJump(nums,n,currPos+maxSteps))\n        maxSteps = maxSteps - 1\n    }\n    return minJump\n}\n   \nint jump(int[] nums, int n) {\n    return decideJump(nums, n, 0)\n}<\/pre>\n\n\n\n<h3 id=\"python--implementation\"><span id=\"python-implementation\">Python <meta charset=\"utf-8\">Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def decideJump(nums, n, currPos):\n    if currPos >=  n-1:\n        return 0\n    minJump = 9999999999999\n    maxSteps = nums[currPos]\n    whilemaxSteps > 0 :\n        minJump = min(minJump, 1 + decideJump(nums,n,currPos+maxSteps))\n        maxSteps = maxSteps - 1\n    return minJump\n \n   \ndef jump(nums, n):\n    return decideJump(nums, n, 0)<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N^N), where N is the total elements in the array.<br><strong>Space Complexity:<\/strong> O(1), since no extra space is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"approach-2-dynamic-programming\">Approach 2: Dynamic Programming<\/h2>\n\n\n\n<p>In the previous approach, if you clearly observe the recursion tree, it can be clearly seen that many of the subproblems are calculated more than once, which in turn takes more time as well as space. Therefore, we can store the answer to such overlapping subproblems in a table and get the answer to this problem in O(1) using a <a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>dynamic programming<\/strong><\/a> approach.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"824\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dynamic Programming\"  class=\"wp-image-3187 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming-1024x824.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming-1024x824.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming-300x241.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming-768x618.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming-1536x1236.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming-2048x1648.png 2048w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming-380x306.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming-550x443.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming-800x644.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming-1160x934.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dynamic-Programming.png 2915w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Create a <strong>dp[]<\/strong> array of size <strong>N<\/strong>, where <strong>N<\/strong> is the size of the given array.<\/li><li>Initialise all the elements of the array to <strong>INT_MAX<\/strong>.<\/li><li>Initialise <strong>dp[0] = 0<\/strong>, since, we are standing at the first index and we need no jumps to reach the first element.<\/li><li>The recursive structure would be:<br><strong>dp[i] = 1 + min(dp[i], 1 + min( dp[i+1], dp[i+2],. . . dp[i + dp[i] + 1]))<\/strong><\/li><li>Iterate a loop from 0 till <strong>N &#8211; 1<\/strong>.<strong> <\/strong>Run a nested loop from <strong>i + 1<\/strong> till <strong>min(i + arr[i] + 1, n)<\/strong> and find the minimum of <strong>jumps[i] <\/strong>and <strong>i + jumps[i]<\/strong>.<\/li><li>After iterations, return the value of <strong>dp[N &#8211; 1]<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c--code-for-dp-method\"><span id=\"c-code-for-dp-method\">C++ <meta charset=\"utf-8\">Code For DP Method<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int minJump(int num[], int n){\n    int dp[n] = {INT_MAX}\n    dp[0] = 0\n    for(i = 0 to i &lt; n){\n        for(j = i+1 to j &lt; min(i+num[i]+1, n)) {\n            dp[j] = min(dp[j], 1 + dp[i])\n        }\n    }\n    return dp[n-1]\n}<\/pre>\n\n\n\n<h3 id=\"java-code-for-dp-method\">Java Code For DP Method<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int minJump(int[] num, int n){\n    int[n] dp = {INT_MAX}\n    dp[0] = 0\n    for(i = 0 to i &lt; n){\n        for(j = i+1 to j &lt; min(i+num[i]+1, n)) {\n            dp[j] = min(dp[j], 1 + dp[i])\n        }\n    }\n    return dp[n-1]\n}<\/pre>\n\n\n\n<h3 id=\"python-code-for-dp-method-\"><span id=\"python-code-for-dp-method\">Python Code For DP Method <\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def minJump(num, n){\n    dp = [n] * (99999999)\n    dp[0] = 0\n    For i in range(n):\n        For j in range(i+1,  min(i+num[i]+1, n)):\n            dp[j] = min(dp[j], 1 + dp[i])\n    return dp[n-1]<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N^ 2), where N is the total elements in the array.<br><strong>Space Complexity:<\/strong> O(N), since <strong>dp[]<\/strong> array is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"approach-3-greedy-approach\">Approach 3: Greedy Approach<\/h2>\n\n\n\n<p>In the previous approach, it was observed that if we are at position <strong>i<\/strong>, the maximum one can jump is <strong>(i,&nbsp; i + nums[i])<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"612\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Greedy Approach\"  class=\"wp-image-3188 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Greedy-Approach-1024x612.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Greedy-Approach-1024x612.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Greedy-Approach-300x179.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Greedy-Approach-768x459.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Greedy-Approach-380x227.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Greedy-Approach-550x329.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Greedy-Approach-800x478.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Greedy-Approach-1160x694.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Greedy-Approach.png 1291w\" ><\/figure>\n\n\n\n<p>In the below example, only can jump in three different positions from the given index <strong>i<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"665\"  height=\"353\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"example\"  class=\"wp-image-3189 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 665px) 100vw, 665px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example.png 665w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example-300x159.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example-380x202.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example-550x292.png 550w\" ><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"472\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Example 2\"  class=\"wp-image-3190 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example1-1024x472.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example1-1024x472.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example1-300x138.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example1-768x354.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example1-380x175.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example1-550x253.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example1-800x369.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example1-1160x535.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/example1.png 1291w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Consider three variables, <strong>jumps<\/strong>, which stores the number of jumps, <strong>end<\/strong>, which denotes the end of the array and <strong>farthest<\/strong> denoting the farthest one can jump and initialise them to 0.<\/li><li>Traverse over the given array and perform the following operation:<ul><li><strong>farthest = i + nums[i]<\/strong><\/li><li>If <strong>end <\/strong>is reached, then <strong>ith<\/strong> jump is finished, therefore update <strong>end = farthest<\/strong>.<\/li><\/ul><\/li><li>Return total jumps.<\/li><\/ul>\n\n\n\n<h3 id=\"c--code-for-greedy-approach\"><span id=\"c-code-for-greedy-approach\">C++ <meta charset=\"utf-8\">Code For Greedy Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int minJump(int nums[], int n) {\n        int jumps = 0, currentJumpEnd = 0, farthest = 0;\n        for (int i = 0; i &lt; n - 1; i++) {\n             farthest = max(farthest, i + nums[i]);\n             if (i == currentJumpEnd) {\n                jumps++;\n                currentJumpEnd = farthest;\n            }\n        }\n        return jumps;\n    }<\/pre>\n\n\n\n<h3 id=\"java--code-for-greedy-approach\"><span id=\"java-code-for-greedy-approach\">Java <meta charset=\"utf-8\">Code For Greedy Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int minJump(int[] nums) {\n        int jumps = 0, currentJumpEnd = 0, farthest = 0;\n        for (int i = 0; i &lt; nums.length - 1; i++) {\n             farthest = Math.max(farthest, i + nums[i]);\n             if (i == currentJumpEnd) {\n                jumps++;\n                currentJumpEnd = farthest;\n            }\n        }\n        return jumps;\n    }<\/pre>\n\n\n\n<h3 id=\"python-code-for-greedy-approach\">Python Code For Greedy Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def minJump(nums):\n        jumps = 0\n        current_jump_end = 0\n        farthest = 0\n        for i in range(len(nums) - 1):\n            farthest = max(farthest, i + nums[i])\n            if i == current_jump_end:\n                jumps += 1\n                current_jump_end = farthest\n        return jumps<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N), where N is the total elements in the array.<br><strong>Space Complexity:<\/strong> O(1), since <strong>dp[]<\/strong> array is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/min-jumps-array\/\" target=\"_blank\" rel=\"noreferrer noopener\">Min Jumps Array<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<ol><li><strong>What is the most efficient approach to solve this problem?<\/strong><strong><br><\/strong>The greedy approach is the most efficient approach since it takes, O(N) time and O(1) space,<\/li><\/ol>\n\n\n\n<ol start=\"2\"><li><strong>What is the recurrence relation of the dynamic programming approach?<br><\/strong>The recurrence relation of the dynamic programming approach is as follows &#8211;<br>&nbsp; &nbsp; &nbsp; &nbsp; dp[i] = 1 + min(dp[i], 1 + min( dp[i+1], dp[i+2],. . . dp[i + dp[i] + 1]))<\/li><\/ol>\n","protected":false},"excerpt":{"rendered":"Minimum Jumps To Reach End of an Array Given an array of non-negative integers, A, of length N.&hellip;\n","protected":false},"author":4,"featured_media":3184,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[457,399,471],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2859"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2859"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2859\/revisions"}],"predecessor-version":[{"id":9816,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2859\/revisions\/9816"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3184"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2859"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2859"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2859"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}