Description
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique
Examples:
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.Solution in Python
Python
from typing import List
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
# Total gas and total cost to check if a solution is possible
total_gas = sum(gas)
total_cost = sum(cost)
# If the total gas is less than the total cost, it's impossible to complete the circuit
if total_gas < total_cost:
return -1
# Initialize starting point and current tank gas
start = 0
current_gas = 0
# Iterate through each gas station
for i in range(len(gas)):
# Update the current tank gas after refilling and traveling to the next station
current_gas += gas[i] - cost[i]
# If at any point, current_gas becomes negative,
# it means we cannot reach this station from the previous start
if current_gas < 0:
# We need to start from the next station
start = i + 1
# Reset current_gas for the new start
current_gas = 0
# The start index is the starting gas station
return startExplanation:
- Initialization:
total_gasandtotal_costare computed to determine if the problem is solvable. If the total amount of gas available is less than the total cost needed to travel the entire route, then it’s impossible to complete the circuit.
- Check Feasibility:
- If
total_gas < total_cost, return-1because the journey cannot be completed.
- If
- Finding the Starting Point:
- Initialize
startto0andcurrent_gasto0. - Iterate over each gas station:
- Calculate the net gas available at each station by subtracting the cost to travel to the next station from the gas available at the current station.
- If
current_gasbecomes negative, it indicates that starting from the currentstartstation can’t reach this station. Thus, update the starting station toi + 1and resetcurrent_gasto0.
- Initialize
- Return Result:
- After the loop,
startwill hold the index of the gas station from which the journey can be started to complete the circuit.
- After the loop,
This approach ensures that we only traverse the list once, making the algorithm efficient with a time complexity of O(n).
Solution in Javascript
JavaScript
/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
var canCompleteCircuit = function(gas, cost) {
// Total gas and total cost to check if a solution is possible
let totalGas = 0;
let totalCost = 0;
// Calculate total gas and total cost
for (let i = 0; i < gas.length; i++) {
totalGas += gas[i];
totalCost += cost[i];
}
// If the total gas is less than the total cost, it's impossible to complete the circuit
if (totalGas < totalCost) {
return -1;
}
// Initialize starting point and current tank gas
let start = 0;
let currentGas = 0;
// Iterate through each gas station
for (let i = 0; i < gas.length; i++) {
// Update the current tank gas after refilling and traveling to the next station
currentGas += gas[i] - cost[i];
// If at any point, currentGas becomes negative,
// it means we cannot reach this station from the previous start
if (currentGas < 0) {
// We need to start from the next station
start = i + 1;
// Reset currentGas for the new start
currentGas = 0;
}
}
// The start index is the starting gas station
return start;
};Solution in Java
Java
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// Total gas and total cost to check if a solution is possible
int totalGas = 0;
int totalCost = 0;
// Calculate total gas and total cost
for (int i = 0; i < gas.length; i++) {
totalGas += gas[i];
totalCost += cost[i];
}
// If the total gas is less than the total cost, it's impossible to complete the circuit
if (totalGas < totalCost) {
return -1;
}
// Initialize starting point and current tank gas
int start = 0;
int currentGas = 0;
// Iterate through each gas station
for (int i = 0; i < gas.length; i++) {
// Update the current tank gas after refilling and traveling to the next station
currentGas += gas[i] - cost[i];
// If at any point, currentGas becomes negative,
// it means we cannot reach this station from the previous start
if (currentGas < 0) {
// We need to start from the next station
start = i + 1;
// Reset currentGas for the new start
currentGas = 0;
}
}
// The start index is the starting gas station
return start;
}
}Solution in C#
C#
public class Solution {
public int CanCompleteCircuit(int[] gas, int[] cost) {
// Total gas and total cost to check if a solution is possible
int totalGas = 0;
int totalCost = 0;
// Calculate total gas and total cost
for (int i = 0; i < gas.Length; i++) {
totalGas += gas[i];
totalCost += cost[i];
}
// If the total gas is less than the total cost, it's impossible to complete the circuit
if (totalGas < totalCost) {
return -1;
}
// Initialize starting point and current tank gas
int start = 0;
int currentGas = 0;
// Iterate through each gas station
for (int i = 0; i < gas.Length; i++) {
// Update the current tank gas after refilling and traveling to the next station
currentGas += gas[i] - cost[i];
// If at any point, currentGas becomes negative,
// it means we cannot reach this station from the previous start
if (currentGas < 0) {
// We need to start from the next station
start = i + 1;
// Reset currentGas for the new start
currentGas = 0;
}
}
// The start index is the starting gas station
return start;
}
}