title: Linear time algorithm for Minimum number of jumps required to reach end
body: <p>Problem: Minimum number of jumps to reach end</p>
  
  <p>Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then we cannot move through that element.</p>
  
  <p>Example:</p>
  
  <p>Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
  Output: 3 (1-> 3 -> 8 ->9)
  First element is 1, so can only go to 3. Second element is 3, so can make at most 3 steps i.e. to 5 or 8 or 9.</p>
  
  <p>Source: <a href="http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/" rel="noreferrer">http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/</a></p>
  
  <p>I have made a linear time algorithm for finding Minimum number of jumps required to reach end of an array.</p>
  
  <p>The source code is as below:</p>
  
  <pre><code>int minJumpsUpdated(int arr[], int n)
  {
    int *jumps = malloc(n * sizeof(int));  // jumps[n-1] will hold the result
    int i =1, j = 0;
  
    jumps[0] = 0;
    for (i = 1; i &lt; n; ) { 
  
      // if i is out of range of arr[j], then increment j
      if (arr[j] + j &lt; i &amp;&amp; j &lt; i) {
  
        j++;
  
      // else if i is within range of arr[j], 
      //   jumps for ith element would be jumps[j]+1
      } else if (arr[j] + j &gt;= i &amp;&amp; j &lt; i) {
  
        jumps[i] = jumps[j] + 1;
        i++;
  
      } else {
        printf("solution does not exist");
        return -1;
      }
    }
  
    printf("jumps: ");
    for (i = 0; i &lt; n; i++) {
      printf("%d, ", jumps[i]);
    }
    return jumps[n - 1];
  }
  </code></pre>
  
  <p>Example:</p>
  
  <p>1.) initially <code>i=1, j=0</code> and <code>arr[] = {1, 3, 6, 1, 0, 9};</code>   </p>
  
  <pre><code>jumps[] = 0,0,0,0,0,0
  </code></pre>
  
  <p>2.) as <code>i</code> is within range of <code>arr[j]</code> ie. <code>i&lt;= j+arr[j]</code>, number of jumps required to go to ith position would be min number of jumps till jth position + 1.  </p>
  
  <pre><code>i=2, j=0, jumps[] = 0,1,0,0,0,0
  </code></pre>
  
  <p>3.) <code>i&gt;j+arr[j]</code> i.e. <code>j++;</code></p>
  
  <pre><code>i=2, j=1, jumps[] = 0,1,0,0,0,0
  </code></pre>
  
  <p>4.) <code>i&lt;=j+arr[j]</code> i.e. <code>jumps[i] = jumps[j]+1;</code> </p>
  
  <pre><code>i=3, j=1, jumps[] = 0,1,2,0,0,0
  </code></pre>
  
  <p>5.) <code>i&lt;=j+arr[j]</code> i.e. <code>jumps[i] = jumps[j]+1;</code></p>
  
  <pre><code>i=4, j=1, jumps[] = 0,1,2,2,0,0
  </code></pre>
  
  <p>6.) <code>i&lt;=j+arr[j]</code> i.e. <code>jumps[i] = jumps[j]+1;</code></p>
  
  <pre><code>i=5, j=1, jumps[] = 0,1,2,2,2,0
  </code></pre>
  
  <p>7.) <code>i&gt;j+arr[j]</code> i.e. <code>j++;</code></p>
  
  <pre><code>i=5, j=2, jumps[] = 0,1,2,2,2,0
  </code></pre>
  
  <p>8.) <code>i&lt;=j+arr[j]</code> i.e. <code>jumps[i] = jumps[j]+1;</code></p>
  
  <pre><code>i=6, j=2, jumps[] = 0,1,2,2,2,3
  </code></pre>
  
  <p>------ END ------</p>
  
  <p>I am not able to figure out under which test case this program will not work. I am asking this because on internet the optimized solution is using DP which is O(n^2). My solution is linear time. i.e. O(n). So I am assuming there are some cases which this algorithm will not handle. So I am curious what cases it does not handle.   </p>
  
  <p>Your help will be appreciated.   </p>
  
  <p>Thank you.</p>