Gas Station Greedy DSA Solution - Study Chapter | QuizMaker

Gas Station explained with O(n^2) simulation, optimized greedy reset, dry run, edge cases, complexity, and Python, C++, Java code.

Read
12m
Type
Chapter
Access
Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 13: Greedy Algorithms

Learning Outcome

After this lesson, you should be able to prove why a failed fuel segment cannot contain a valid start.

Problem Statement

Given gas and cost arrays, return the start index that lets you complete the circuit, or -1 if impossible.

InputOutputWhy
gas = [1,2,3,4,5], cost = [3,4,5,1,2]3Starting at index 3 gives enough fuel to complete the full loop.

Brute Force Approach

Try every station as a start and simulate the full circuit. This costs O(n^2).

Optimized Approach

Track total fuel and a local tank. If the local tank becomes negative at i, no start from the current candidate through i can work, so reset start to i + 1.

Exact Pseudocode

total = 0
tank = 0
start = 0
for i from 0 to n - 1:
  diff = gas[i] - cost[i]
  total += diff
  tank += diff
  if tank < 0:
    start = i + 1
    tank = 0
if total < 0:
  return -1
return start

Reference Code

class Solution:
    def canCompleteCircuit(self, gas, cost):
        total = 0
        tank = 0
        start = 0

        for i in range(len(gas)):
            diff = gas[i] - cost[i]
            total += diff
            tank += diff
            if tank < 0:
                start = i + 1
                tank = 0

        return -1 if total < 0 else start
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0;
        int tank = 0;
        int start = 0;

        for (int i = 0; i < gas.size(); i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            tank += diff;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }

        return total < 0 ? -1 : start;
    }
};
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int tank = 0;
        int start = 0;

        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            tank += diff;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }

        return total < 0 ? -1 : start;
    }
}

Sample Dry Run

StepStateResult
Indexes 0 to 2tank becomes negative repeatedlystart moves forward
Index 3diff = 3start = 3, tank positive
Index 4tank remains positivecandidate survives
Total checktotal fuel is non-negativereturn 3

Complexity

MeasureValueReason
TimeO(n)The arrays are scanned once.
SpaceO(1)Only total, tank, and start are stored.

Edge Cases

Interview Checklist

FAQs

Why can we skip starts before i + 1?

If the tank from the candidate start to i is negative, any start inside that segment has even less helpful prefix fuel.

Why still need total?

A local candidate can survive, but the whole circuit is impossible if total fuel is negative.

What is the core pattern?

Greedy reset after a failed segment.

Tags

Open on QuizMaker