Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Gas Station

Greedymedium

Given `gas` and `cost` arrays, implement `canCompleteCircuit(gas, cost)` returning the starting index from which you can travel the full circle once, or `-1` if impossible. A unique answer exists when possible.

Sample tests

Input: canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])
Output: 3
Input: canCompleteCircuit([2,3,4], [3,4,3])
Output: -1

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Returning the first non-negative station without the feasibility check.

Learning resources

  • Wikipedia: Greedy algorithm
Approach & explanation (try first)

A single greedy pass identifies the unique start in O(n) time.

Loading...
⌘/Ctrl + Enter

Run your code to see results.