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

To travel through the entire circle, the total amount of gas must be greater than the total amount of cost, ensuring a starting point exists. Let’s set the starting point to start = 0 and proceed from there.

At each station, we check if the current gas value is greater than the cost value. If so, we move on to the next station. We calculate the remaining gas plus the current gas minus the cost to see if it’s greater than 0.

If it is greater than 0, we continue moving forward.
If it’s less than 0 when we reach a certain station, it means that any point from the starting point to this point cannot be used as the starting point. (This is due to mathematical proof.)

In this case, we set the starting point as the next point and continue traversing. When we traverse the entire ring, we save the currently set 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;
	    }
	}
}

// OJ: https://leetcode.com/problems/gas-station
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int tank = 0, total = 0, ans = 0, N = gas.size();
        for (int i = 0; i < N; ++i) {
            total += gas[i] - cost[i];
            if ((tank += gas[i] - cost[i]) < 0) {
                tank = 0;
                ans = i + 1;
            }
        }
        return total < 0 ? -1 : ans;
    }
};

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        i = j = n - 1
        cnt = s = 0
        while cnt < n:
            s += gas[j] - cost[j]
            cnt += 1
            j = (j + 1) % n
            while s < 0 and cnt < n:
                i -= 1
                s += gas[i] - cost[i]
                cnt += 1
        return -1 if s < 0 else i

############

class Solution(object):
  def canCompleteCircuit(self, gas, cost):
    """
    :type gas: List[int]
    :type cost: List[int]
    :rtype: int
    """

    totalgas = 0
    totalcost = 0
    start = 0
    balance = 0
    for i in range(0, len(gas)):
      totalgas += gas[i]
      totalcost += cost[i]

    for i in range(0, len(gas)):
      balance += gas[i] - cost[i]
      if balance < 0:
        start = i + 1
        balance = 0

    if totalcost <= totalgas:
      return start
    return -1

134 - Gas Station

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions