Reference: LeetCode EPI 17.6
Difficulty: Medium

My Post: Java B-F/Greedy Solutions with Explanation, Comments and Illustration (easy-understand)

Problem

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i + 1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

  • If there exists a solution, it is guaranteed to be unique.
  • Both input arrays are non-empty and have the same length.
  • Each element in the input arrays is a non-negative integer.

Example: 

1
2
3
4
5
6
7
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3

gas  = [3,3,4]
cost = [3,4,4]
Output: -1

Analysis

Brute-Force

The idea of brute-force is to examine each single station (or city in EPI book):

  • Choose the station as a starting point.
  • Simulate the road trip to see if the following stations are reachable.

Note: See comments.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int canCompleteCircuit(int[] gas, int[] cost) {
  int n = gas.length; // #station
  for (int i = 0; i < n; ++i) { // for each station i (starting point)
    int gallon = gas[i]; // refuel at starting point
    boolean isAmple = true; // isAmple: is it a valid starting point
    for (int j = 0; j < n; ++j) { // we need to check n stations
      // note: nextStation is the one we need to check
      //       currStation is denoted because the cost information is in it
      int currStation = (i + j) % n;
      int nextStation = (currStation + 1) % n;
      gallon -= cost[currStation];
      if (gallon < 0) { // not reachable from currStation to nextStation
        isAmple = false;
        break;
      }
      gallon += gas[nextStation]; // refuel in nextStation
    }
    if (isAmple) return i;
  }
  return -1;
}

Time: $O(N^2)$
Space: $O(1)$

Greedy

Proof by Contradiction: LeetCode Solution (if you have time)

The illustration in the EPI book helps understand the algorithm.

Note: The problem statement is a bit different, but the idea is the same. (Distance equals Gas Cost, City equals Station)

Starting at A, Reference: EPI

We can see that at D we have the lowest gallon before refueling (negative gallon is allowed in the algorithm). Now take the station D as the starting point then we can have the optimal solution (if it exists).

Starting at D, Reference: EPI

At last, check the starting point at last to see if such an ample station exists. If the gallon at last is negative which means we don’t have enough gallons in total to do the road trip (return -1).

Note: See comments.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int canCompleteCircuit(int[] gas, int[] cost) {
  int n = gas.length;
  int minCityIdx = -1;
  int gallon = 0, minGallon = Integer.MAX_VALUE;
  for (int i = 0; i < n; ++i) { // starting from city 0
    gallon += gas[i]; // refuel at i
    gallon -= cost[i]; // deduct cost from i to i + 1
    // update
    if (gallon < minGallon) {
      minGallon = gallon;
      minCityIdx = (i + 1) % n; // consider the calculation for starting point at last
    }
  }
  // when getting back to the starting point, check if the gallon is negative (no ample city)
  return (gallon >= 0) ? minCityIdx : -1;
}

Time: $O(N)$
Space: $O(1)$