Gas Station

Asked byAmazonIBMMicrosoftAppletiktokWalmart Global Tech

Problem

Given gas[i] (fuel available at station i) and cost[i] (fuel required to travel from station i to the next), determine the starting station index from which you can complete a full circuit in one direction without running out of fuel, or -1 if it's impossible. A solution, if it exists, is guaranteed to be unique.

Examples

Example 1

Input:gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Output:3

Constraints

n == gas.length == cost.length
1 <= n <= 10^5

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Greedy pattern

Make the choice that looks best right now, without reconsidering it later, and trust that a sequence of locally optimal choices adds up to a globally optimal answer. It only works when the problem actually has that property.

Look for this pattern when

Sorting the input by some key, then making one pass with simple local decisions, intuitively seems to produce the best answer.
The problem involves intervals, scheduling, or resource allocation where "always take the best available option" tends to work.

Read the full Greedy guide →

Video walkthroughs

Original problem on LeetCode ↗