Gas Station Circuit
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
n gas stations sit on a circular road. Station i provides gas[i] fuel and driving to station (i + 1) % n costs cost[i].
Starting with an empty tank (unlimited capacity), you want to drive once around in increasing order. Return the smallest
starting station that completes the circuit without the fuel ever going negative, or -1 if none does.
Examples
| gas | cost | result |
|---|---|---|
[1, 2, 3, 4, 5] | [3, 4, 5, 1, 2] | 3 |
[2, 3, 4] | [3, 4, 3] | -1 |
[5, 0, 5] | [5, 0, 5] | 0 |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(gas: int[], cost: int[]) → int
Constraints
-
gas.lengthcost.length -
gas[i],cost[i]
Expected complexity
- Time
- O(N)
- Space
- O(1)
Examples
| gas | cost | Expected |
|---|---|---|
[1,2,3,4,5] | [3,4,5,1,2] | 3 |
[2,3,4] | [3,4,3] | -1 |
[5,0,5] | [5,0,5] | 0 |
Hint
Hint
If sum(gas) >= sum(cost) an answer exists. If the tank first goes negative at i when starting from s, no start in
s..i works, so restart from i + 1 with an empty tank. One pass finds the smallest valid start. Simulating every start is
and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1152 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 5 | verdict only |