Gas Station
Gas Station Problem: Finding the Starting Point of a Circular Route
The Gas Station problem is a classic puzzle that challenges us to identify the optimal starting point on a circular route where a car can complete the journey without running out of fuel.
This problem involves calculating gas availability and travel costs while adhering to specific constraints.
Problem Description
You are given two arrays:
- gas: Represents the amount of gas available at each station.
- cost: Represents the gas required to travel to the next station.
The car starts with an empty tank, and your task is to return the index of the starting gas station that allows completing a full circuit in the clockwise direction. If completing the circuit is impossible, return -1.
Key Guarantee:
- There is at most one solution.
Example 1
Input: nums = [2,-3,4,-2,2,1,-1,4]
Output: 8
Explanation:
The subarray [4,-2,2,1,-1,4] has the largest sum 8.
Example 2
Input: nums = [-1]
Output: -1
Constraints:
- 1 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
Solution Approach
To solve the problem efficiently, we use a greedy algorithm with two key observations:
Total Gas vs Total Cost:
- If the total gas available is less than the total cost, completing the circuit is impossible.
Tracking Local Feasibility:
- If the car runs out of gas at any point, the journey cannot start from any station between the previous starting station and the current station.
- Reset the starting point to the next station and continue.
Algorithm
Calculate the Total Gas and Cost:
- Compute the difference (
tank) at each station: tank=gas[i]−cost[i]\text{tank} = \text{gas[i]} – \text{cost[i]} - Track the cumulative
tankto determine if completing the circuit is feasible.
- Compute the difference (
Identify the Starting Station:
- If the car runs out of gas (
tank < 0), reset the starting point to the next station and reset thetank.
- If the car runs out of gas (
Return the Result:
- If the total gas is greater than or equal to the total cost, return the starting index. Otherwise, return
-1.
- If the total gas is greater than or equal to the total cost, return the starting index. Otherwise, return
There are mainly Four approach to solve this problem –
- Brute Force
- Sweep Line Algorithm
- Min Heap
- Min Segment Tree (Lazy Propagation)
1. Brute Force
- Time complexity: O(n^2)
- Space complexity: O(1)
Python
C++
Java
JavaScript
Python
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
for i in range(n):
tank = gas[i] - cost[i]
if tank < 0:
continue
j = (i + 1) % n
while j != i:
tank += gas[j]
tank -= cost[j]
if tank < 0:
break
j += 1
j %= n
if j == i:
return i
return -1C++
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
int n = gas.size();
for (int i = 0; i < n; i++) {
int tank = gas[i] - cost[i];
if (tank < 0) continue;
int j = (i + 1) % n;
while (j != i) {
tank += gas[j] - cost[j];
if (tank < 0) break;
j = (j + 1) % n;
}
if (j == i) return i;
}
return -1;
}
}; Java
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int i = 0; i < n; i++) {
int tank = gas[i] - cost[i];
if (tank < 0) continue;
int j = (i + 1) % n;
while (j != i) {
tank += gas[j] - cost[j];
if (tank < 0) break;
j = (j + 1) % n;
}
if (j == i) return i;
}
return -1;
}
}JavaScript
class Solution {
/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
canCompleteCircuit(gas, cost) {
const n = gas.length;
for (let i = 0; i < n; i++) {
let tank = gas[i] - cost[i];
if (tank < 0) continue;
let j = (i + 1) % n;
while (j !== i) {
tank += gas[j] - cost[j];
if (tank < 0) break;
j = (j + 1) % n;
}
if (j === i) return i;
}
return -1;
}
}2. Two Pointers
Time & Space Complexity
- Time complexity: O(n)
- Space complexity: O(1)
C++
Java
Python
JavaScript
C++
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
int n = gas.size();
int start = n - 1, end = 0;
int tank = gas[start] - cost[start];
while (start > end) {
if (tank < 0) {
start--;
tank += gas[start] - cost[start];
} else {
tank += gas[end] - cost[end];
end++;
}
}
return tank >= 0 ? start : -1;
}
}; Java
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
start, end = n - 1, 0
tank = gas[start] - cost[start]
while start > end:
if tank < 0:
start -= 1
tank += gas[start] - cost[start]
else:
tank += gas[end] - cost[end]
end += 1
return start if tank >= 0 else -1
Python
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
start, end = n - 1, 0
tank = gas[start] - cost[start]
while start > end:
if tank < 0:
start -= 1
tank += gas[start] - cost[start]
else:
tank += gas[end] - cost[end]
end += 1
return start if tank >= 0 else -1JavaScript
class Solution {
/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
canCompleteCircuit(gas, cost) {
const n = gas.length;
let start = n - 1, end = 0;
let tank = gas[start] - cost[start];
while (start > end) {
if (tank < 0) {
start--;
tank += gas[start] - cost[start];
} else {
tank += gas[end] - cost[end];
end++;
}
}
return tank >= 0 ? start : -1;
}
}3. Greedy
Time & Space Complexity
- Time complexity: O(n)
- Space complexity: O(1)
C++
Java
Python
JavaScript
C++
class Solution {
public:
int canCompleteCircuit(vector& gas, vector& cost) {
if (accumulate(gas.begin(), gas.end(), 0) <
accumulate(cost.begin(), cost.end(), 0)) {
return -1;
}
int total = 0;
int res = 0;
for (int i = 0; i < gas.size(); i++) {
total += (gas[i] - cost[i]);
if (total < 0) {
total = 0;
res = i + 1;
}
}
return res;
}
}; Java
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
if (Arrays.stream(gas).sum() < Arrays.stream(cost).sum()) {
return -1;
}
int total = 0;
int res = 0;
for (int i = 0; i < gas.length; i++) {
total += (gas[i] - cost[i]);
if (total < 0) {
total = 0;
res = i + 1;
}
}
return res;
}
}
Python
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if sum(gas) < sum(cost):
return -1
total = 0
res = 0
for i in range(len(gas)):
total += (gas[i] - cost[i])
if total < 0:
total = 0
res = i + 1
return resJavaScript
class Solution {
/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
canCompleteCircuit(gas, cost) {
if (gas.reduce((acc, val) => acc + val, 0) <
cost.reduce((acc, val) => acc + val, 0)) {
return -1;
}
let total = 0;
let res = 0;
for (let i = 0; i < gas.length; i++) {
total += gas[i] - cost[i];
if (total < 0) {
total = 0;
res = i + 1;
}
}
return res;
}
}
