CareerCup

The brute force is exponential; however, the solution below has TC = O(n^2) and SC = O(n).

import java.util.Arrays;
import java.util.Collections;

class GasStation implements Comparable<GasStation> {
    double distance;
    double fuelGallons;

    public GasStation(double distance, double fuelGallons) {
        this.distance = distance;
        this.fuelGallons = fuelGallons;
    }

    @Override
    public int compareTo(GasStation o) {
        return Double.compare(this.distance, o.distance);
    }
}

public class GasStationStops {
    public static final int INSUFFICIENT_CREDIT = -1;
    public static final int NO_EXACT_MATCH = -2;

    static int find(GasStation[] gasStations, double availableGallons, double maxDistance) {
        if (gasStations == null || gasStations.length == 0) {
            return INSUFFICIENT_CREDIT;
        }
        Arrays.sort(gasStations, Collections.reverseOrder());
        if (maxDistance < gasStations[0].distance) {
            return INSUFFICIENT_CREDIT;
        }

        double[] requiredGallons = new double[gasStations.length + 1];
        double currentDistance = 0.0;
        int reGlIndx = 1;
        for (int gasStIndx = gasStations.length - 1; gasStIndx >= 0; gasStIndx--) {
            GasStation gasStation = gasStations[gasStIndx];
            updateRequiredGallons(requiredGallons, reGlIndx, gasStation.distance - currentDistance, gasStation.fuelGallons);
            currentDistance = gasStation.distance;
            reGlIndx++;
        }
        double distanceToFirstLocation = maxDistance - gasStations[0].distance;
        System.out.print(Arrays.toString(requiredGallons));
        return binarySearch(requiredGallons, availableGallons - distanceToFirstLocation, 0, requiredGallons.length - 1);
    }

    private static void updateRequiredGallons(double[] requiredGallons, int reGlIndx, double delta, double moreGallons) {
        for (int i = 0; i < reGlIndx; i++) {
            requiredGallons[i] += delta;
        }
        requiredGallons[reGlIndx] = requiredGallons[reGlIndx - 1] - moreGallons;
        for (int j = reGlIndx - 1; j > 0; j--) {
            requiredGallons[j] = Math.min(requiredGallons[j - 1] - moreGallons, requiredGallons[j]);
        }
    }

    private static int binarySearch(double[] a, double target, int i, int j) {
        if (i < 0 || i >= a.length || j < 0 || j >= a.length || i > j)
            return NO_EXACT_MATCH;

        int m = (i + j) / 2;
        if (a[m] == target)
            return m;

        int p;
        if (target < a[m]) {
            p = binarySearch(a, target, m + 1, j);
            if (p == NO_EXACT_MATCH) {
                return m < a.length - 1 ? m + 1 : INSUFFICIENT_CREDIT;
            }
        } else {
            p = binarySearch(a, target, i, m - 1);
            if (p == NO_EXACT_MATCH) {
                return m;
            }
        }
        return p;
    }

    public static void main(String[] args) {
        print(find(null, 10, 20));
        print(find(new GasStation[]{}, 10, 20));
        print(find(new GasStation[]{
                new GasStation(16, 3),
                new GasStation(10, 7),
                new GasStation(14, 11),
                new GasStation(11, 5),
                new GasStation(7, 6)}, 10, 20));
        print(find(new GasStation[]{
                new GasStation(15, 4),
                new GasStation(10, 7),
                new GasStation(5, 3)}, 10, 20));
        print(find(new GasStation[]{
                new GasStation(10, 7),
                new GasStation(15, 4),
                new GasStation(5, 3)}, 10, 20));
        print(find(new GasStation[]{
                new GasStation(10, 7),
                new GasStation(15, 4),
                new GasStation(5, 3)}, 6, 20));
        print(find(new GasStation[]{
                new GasStation(10, 7),
                new GasStation(15, 4),
                new GasStation(5, 3)}, 9, 20));
        print(find(new GasStation[]{
                new GasStation(10, 7),
                new GasStation(15, 4),
                new GasStation(5, 3)}, 12, 20));
        print(find(new GasStation[]{
                new GasStation(10, 7),
                new GasStation(15, 4),
                new GasStation(5, 3)}, 13, 20));
        print(find(new GasStation[]{
                new GasStation(10, 6),
                new GasStation(15, 3),
                new GasStation(5, 1)}, 10, 20));
        print(find(new GasStation[]{
                new GasStation(10, 1),
                new GasStation(15, 1),
                new GasStation(5, 1)}, 10, 20));
    }

    static void print(int x) {
        if (x == INSUFFICIENT_CREDIT) {
            System.out.println("Min # Stops:INSUFFICIENT INITIAL GALLONS");
        } else {
            System.out.println(", Min # Stops:" + x);
        }
    }
}

If you have :
eg: gas = 10 , distance = 20
gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}

Then how can you opt for 14,11? because the initial gas itself is 10, Hence the only option for you is either , 10,7 or 7,6

I can think of Backtrack as one of the way to solve this

gasStation[] = {{16,3}, {10, 7}, {14, 11},{11, 5}, {7, 6}}

-Sort gasStation on the basis of remaining distance.
-Now start traversing from biggest remaining distance gas station to lower
-Keep track of upto what max distance we can ride in case opt for current gas station
-In case max distance capability is higher than previous max distance, override it else ignore
-Keep traversing upto distance current fuel capacity allows and we have our first stop to help us on longest ride in one gas filling stay. Save it in a list.
-Repeat all above step and keep adding optimal gas filling station in list.
-At the end we have all the required stops in list.

Time complexity:
=> Sorting: n log(n) + Traversing: n
=> n log (n)

Similar to leetcode 45 Jump Game II.

Generally it would be a dynamic programming solution. We either include the station or exclude it. 1) if we include the station, we add 1 stop to the result and add all gas; 2) if we exclude it, we add 0 stops and 0 gas. Something like this:

var incl = 1 + minStops(startIndex + 1, remainingGas + stations[startIndex].gas);
var excl = minStops(startIndex + 1, remainingGas);
return Math.min(incl, excl);

This would be O(N^2) with memoization because each function has 2 parameters.

But for some reason a greedy algorithm works here. Greedy algorithms almost never work, in 99% of cases dynamic programming is better, but this question for some reason is different. There should be a formal proof why a greedy algorithm works here, but I can't find it and can't prove it myself. But in the result it will be O(n):

var stations = [
  {pos: 16, gas: 3},
  {pos: 10, gas: 7},
  {pos: 14, gas: 11},
  {pos: 11, gas: 5},
  {pos: 7, gas: 6}
];
stations.push({pos: 20, gas: 10}); // add initial stop
stations.push({pos: 0, gas: 0}); // add final stop
console.log('min stops to take: ' + minStopsGreedy(stations));

function minStopsGreedy(stations) { 
  // Sort by position descending
  stations.sort((a, b) => b.pos - a.pos);

  var lastStepReach = 0;
  var currentStepReach = 0;
  var step = 0;

  for (var i = 0; i < stations.length; i++) {
    var distFromStart = stations[0].pos - stations[i].pos;
    if (distFromStart > lastStepReach) {
      step++;
      lastStepReach = currentStepReach;
    }

    currentStepReach =
        Math.max(currentStepReach, lastStepReach + stations[i].gas);
  }

  if (currentStepReach < stations[0].pos) {
    return Infinity;
  }

  return step;
}

struct station
{
int dist;
inr gas;
};
int Find( station gasStation[], int dist, int gas, int n)
{
//sort gas station array w.r.t to its gas quantity.
//{(14,11) ,(10,7) ,(7,6),(11,5),(16,3)}
sort(gasStation , 0 , n);
int count = 0;
for(int i = 0; i < n; i++)
{
if(dist - gasStation[i].dist > gas)
continue;
gas = dist - gasStation[i].dist + gasStation[i].gas;
dist = gasStation[i].dist;
count++;
if(gas >= dist)
return count;
}
return -1;

871. Minimum Number of Refueling Stops in leetcode
has both dp and greedy solution approaches