title: Car Fueling Problem (Greedy Algorithm), Nested while loop with O(n) complexity
body: <p>Input</p>
  <blockquote>
  <p>(1) the maximum distance that a car can travel with a full tank: L km;</p>
  <p>(2) an integer array, [0, x1, x2, …, xn, xn+1], each integer represents the distance between a location and a source point A. The first integer is 0, which is the distance between A and A. The second distance x1, represents the distance between the first gas station and A. There are n gas stations between A and B (the destination). xn is the distance between the last gas station and A, and xn+1 is the distance between B and A.</p>
  <p>(3) n, which is the number of gas stations.</p>
  </blockquote>
  <p>Output</p>
  <blockquote>
  <p>The minimum number of refills to get from A to B</p>
  </blockquote>
  <p>Code</p>
  <pre><code>numRefills = 0
  currentPosition = 0
  
  while(currentPosition &lt;= n){
      lastPosition = currentPosition
  
      while(currentPosition &lt;= n  &amp;&amp;  x[currentPosition + 1] – x[lastPosition] &lt;= L) {
      currentPosition++;
      }
  
      if (currentPosition == lastPosition) return IMPOSSIBLE; 
      if (currentPosition &lt;= n) numRefills ++;
  }
  
  return numRefills
  </code></pre>
  <p>My doubts are:</p>
  <blockquote>
  <ol>
  <li>Why is the time-complexity of the above code is O(n)? shouldn't it be O(n^2) at least because of nested while loops?</li>
  <li>How to prove that &quot;Refilling at farthest reachable gas&quot; is a safe move?</li>
  <li>Are there any alternatives to writing the same code but using for loop?</li>
  </ol>
  </blockquote>
  <p>(In short, I understood the logic but I am not able to compute it)</p>
  <p>Any resources/help/hint/guidance is greatly appreciated!</p>