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.

Input	Output	Why
`gas = [1,2,3,4,5], cost = [3,4,5,1,2]`	`3`	Starting 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

Step	State	Result
Indexes 0 to 2	tank becomes negative repeatedly	start moves forward
Index 3	diff = 3	start = 3, tank positive
Index 4	tank remains positive	candidate survives
Total check	total fuel is non-negative	return 3

Complexity

Measure	Value	Reason
Time	O(n)	The arrays are scanned once.
Space	O(1)	Only total, tank, and start are stored.

Edge Cases

If total gas is less than total cost, return -1.
The answer is unique in the standard version when one exists.
Reset start only after local tank becomes negative.

Interview Checklist

Track total feasibility separately from local tank.
Reset candidate start to i + 1 on local failure.
Return -1 when total is negative.

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.