Funcia
Lv.2arraygreedy

Gas Station Circuit

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

gascostresult
[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

  • 1≤n=1 \le n = gas.length == cost.length ≤200,000\le 200{,}000
  • 0≤0 \le gas[i], cost[i] ≤10,000\le 10{,}000

Expected complexity

Time
O(N)
Space
O(1)

Examples

gascostExpected
[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 O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251152 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance605verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.