Question

Formatted question description: https://leetcode.ca/all/134.html

134	Gas Station

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, otherwise return -1.

Note:
The solution is guaranteed to be unique.


Example 1:

Input:
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.


Example 2:

Input:
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.


@tag-greedy

Algorithm

First of all, it is necessary to know that the prerequisite for being able to travel through the entire circle is that the total amount of gas is greater than the total amount of cost, so that there is a starting point.

Suppose you start to set the starting point start = 0, and proceed from here, if the current gas value is greater than the cost value, you can move on. At this time to the next station, the remaining gas plus the current gas minus the cost to see if it is greater 0,

  • if greater than 0, continue to move forward.
  • if this value is less than 0 when reaching a certain station, it means that any point from the starting point to this point cannot be used as the starting point, (why? some math proof)
  • then the starting point is set as the next point and the traversal continues. When traversing the entire ring, the currently saved starting point

Code

Java

public class Gas_Station {

	public class Solution {
	    public int canCompleteCircuit(int[] gas, int[] cost) {

	        // skip valid check
	        if (gas.length == 0) {
	            return 0;
            }

	        int[] diff = new int[gas.length];
	        for (int i = 0; i < diff.length; i++) {
	            diff[i] = gas[i] - cost[i]; // meaning gas left when arriving next station
	        }

	        int sum = 0;
	        int total = 0;
	        int index = 0;
	        for (int i = 0; i < diff.length; i++) {

	            sum += diff[i];
	            total += diff[i];

	            if (sum < 0)    {
	                sum = 0;
	                index = i + 1; // sum from last loop, i-1, current is pointing to i
	            }

	        }

	        return total >= 0? index : -1;
	    }
	}
}

All Problems

All Solutions