Gas Station

Medium · Greedy

You are given two arrays of the same length representing a circular route of gas stations: gas[i] is the amount of fuel available at station i, and cost[i] is the fuel needed to drive from station i to the next one. You start with an empty tank at whichever station you choose. Return the index of the station you must start from so that, driving around the whole circuit once in order, your tank never goes negative. If no such starting station exists, return -1. It is guaranteed that at most one starting index works.

Examples

Input:  gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Why:    Starting the loop at station index 3 leaves enough fuel at every stop to reach the next one all the way around.

Input:  gas = [2,3,4], cost = [3,4,3]
Output: -1
Why:    No matter which station you start from, the tank runs dry before completing the full loop.

Input:  gas = [5,1,2,3,4], cost = [4,4,1,5,1]
Output: 4
Why:    Starting at station 4 keeps the running fuel balance non-negative all the way around the circuit.

Constraints

1 <= gas.length == cost.length <= 10^5, 0 <= gas[i], cost[i] <= 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Gas Station

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Gas Station. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.