Problems/Greedy/Gas Stations
Greedy
medium

Gas Stations

Imagine a circular race track where cars need fuel to complete laps. This problem asks you to find a starting point on the track that allows a car with a limited fuel capacity to complete the entire circuit without running out of fuel, testing your ability to apply greedy algorithms.

arraygreedyoptimizationcircular array

Problem Statement

You are given a circular route with several pit stops. Each pit stop provides a certain amount of fuel, and traveling from one pit stop to the next consumes a specific amount of fuel. You have a car with an unlimited fuel tank, but it starts empty. Determine the starting pit stop that enables you to complete the entire circuit exactly once, without the fuel level ever dropping below zero. If such a starting point exists, return its index; otherwise, return -1.

Example 1
Input: fuel = [5, 1, 2, 4, 3], cost = [5, 2, 2, 1, 2]
Output: 3
Starting at pit stop 3 allows us to complete the circuit: Fuel at 3: 4, cost to 4: 1, tank = 3. Fuel at 4: 3, cost to 0: 2, tank = 4. Fuel at 0: 5, cost to 1: 5, tank = 4. Fuel at 1: 1, cost to 2: 2, tank = 3. Fuel at 2: 2, cost to 3: 2, tank = 3. We completed the circuit.
Example 2
Input: fuel = [1, 2, 3, 4, 5], cost = [2, 3, 4, 5, 1]
Output: 4
Starting at pit stop 4 allows us to complete the circuit: Fuel at 4: 5, cost to 0: 1, tank = 4. Fuel at 0: 1, cost to 1: 2, tank = 3. Fuel at 1: 2, cost to 2: 3, tank = 2. Fuel at 2: 3, cost to 3: 4, tank = 1. Fuel at 3: 4, cost to 4: 5, tank = 0. We completed the circuit.
Constraints
  • -1 <= len(fuel) == len(cost) <= 10^5
  • -0 <= fuel[i], cost[i] <= 10^4
  • -fuel and cost arrays are of the same length
  • -It is guaranteed that there will be at most one solution.

Brute Force Approach

The brute force approach involves trying every pit stop as a starting point and simulating the journey around the circuit. For each starting point, you would track the fuel level and check if it ever drops below zero. If you complete the circuit without running out of fuel, that starting point is the solution. Otherwise, you try the next one. This is like trying every possible starting line in a race to see if you can make it all the way around.

TimeO(n^2)
SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem