Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

871. Minimum Number of Refueling Stops

Time: $O(n^2)$

Space: $O(n)$

			


class Solution {
 public:
  int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
    // dp[i] := farthest position we can reach w/ i refuels
    vector<long> dp(stations.size() + 1);
    dp[0] = startFuel;

    for (int i = 0; i < stations.size(); ++i)
      for (int j = i + 1; j > 0; --j)
        if (dp[j - 1] >=
            stations[i][0])  // With j - 1 refuels, we can reach stations[i][0]
          dp[j] = max(dp[j], dp[j - 1] + stations[i][1]);

    for (int i = 0; i < dp.size(); ++i)
      if (dp[i] >= target)
        return i;

    return -1;
  }
};




			


class Solution {
  public int minRefuelStops(int target, int startFuel, int[][] stations) {
    // dp[i] := farthest position we can reach w/ i refuels
    long dp[] = new long[stations.length + 1];
    dp[0] = startFuel;

    for (int i = 0; i < stations.length; ++i)
      for (int j = i + 1; j > 0; --j)
        if (dp[j - 1] >= stations[i][0]) // With j - 1 refuels, we can reach stations[i][0]
          dp[j] = Math.max(dp[j], dp[j - 1] + stations[i][1]);

    for (int i = 0; i < dp.length; ++i)
      if (dp[i] >= target)
        return i;

    return -1;
  }
}




			


class Solution:
  def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
    # dp[i] := farthest position we can reach w / i refuels
    dp = [startFuel] + [0] * len(stations)

    for i, station in enumerate(stations):
      for j in range(i + 1, 0, -1):
        if dp[j - 1] >= station[0]:  # With j - 1 refuels, we can reach stations[i][0]
          dp[j] = max(dp[j], dp[j - 1] + station[1])

    for i, d in enumerate(dp):
      if d >= target:
        return i

    return -1