Gas Station

MediumGreedygreedy

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

There are n gas stations arranged in a circle. You are given two integer arrays of length n: - gas[i] is the amount of fuel available at station i. - cost[i] is the amount of fuel needed to drive from station i to the next station, i + 1 (and from the last station back to station 0). You start with an empty tank at one of the stations and want to drive clockwise all the way around the circle exactly once, returning to your starting station. At each station you first collect that station's gas[i], then spend cost[i] to reach the next station. Your tank may hold an unlimited amount of fuel, but it can never drop below zero at any point along the way. Return the index of the starting station from which you can complete the full loop. If completing the loop is impossible from any station, return -1. It is guaranteed that if a valid starting station exists, it is **unique**.

Examples

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Start at station 3. Tank: pick up 4 -> 4, drive to 4 costs 1 -> 3. Pick up 5 -> 8, drive to 0 costs 2 -> 6. Pick up 1 -> 7, drive to 1 costs 3 -> 4. Pick up 2 -> 6, drive to 2 costs 4 -> 2. Pick up 3 -> 5, drive to 3 costs 5 -> 0. The tank never goes negative, so 3 works. No other start does.
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Total gas is 9 and total cost is 10, so there is not enough fuel to ever complete the loop from any station.
Input: gas = [5], cost = [4]
Output: 0
A single station: collect 5, spend 4 to drive around back to itself with 1 unit to spare.

Constraints

  • `n == gas.length == cost.length`
  • `1 <= n <= 10^5`
  • `0 <= gas[i], cost[i] <= 10^4`
  • If a solution exists, it is guaranteed to be unique.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More greedy problems