The O(n) Club: Gas Station — Why Your Algorithm’s Tank Keeps Running Empty

The O(n) Club: Gas Station — Why Your Algorithm’s Tank Keeps Running Empty

⚡ TL;DR

Need to drive around a circle of gas stations without running dry? Don’t try every starting point like a desperate Uber driver. Just tally the total fuel vs. cost, sweep once with a greedy tank check, and let Java handle the rest:

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

🧠 How Devs Usually Mess This Up

You’d think an array loop is easy until you see these classics popping up in code reviews:

• Brute Force Brake Burn: Looping from every station. It works. Eventually. When you’re 90.
• The Phantom Multistart: Searching for several starts. Spoiler: there can be only one. Thanks, problem setters!
• Math Blindness: Not checking if total gas even covers total cost before the marathon – that’s how you end up marooned, weeping in technical debt.

🔍 What’s Actually Going On

Picture yourself as a delivery robot with anxiety issues. Each gas station gives you a snack (gas), and each drive uses up energy (cost). If your total snacks aren’t enough, you’re doomed from the start. If they are, there’s a specific moment when your robot heart gives up: whenever the tank drops below zero, you know you couldn’t have started at—or before—that point. The solution? Just reset your optimism (and start position) to the next station after you run empty. Greedy, a little dramatic, but it works.

🛠️ PseudoCode

• Add up the total difference (gas – cost) for all stations:
  total += gas[i] - cost[i];
  If total is negative, game over.
• Maintain your running tank level:
  tank += gas[i] - cost[i];
• If tank dips below zero, reset:
  if (tank < 0) { tank = 0; start = i + 1; }
  You’re officially pretending the struggle never happened.
• At the finish line:
  If total >= 0, start is your sole hero. If not, return -1 and call AAA.

💻 The Code

public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) {
            tank = 0;
            start = i + 1;
        }
    }
    return total >= 0 ? start : -1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Total Gas FOMO: If total gas is less than total cost, you’re not getting home. Don’t even start. Return -1 immediately.
• Boring Case: One station? Just don’t off-by-one yourself on array access. Java won’t send you flowers if you do.
• Too Many Resets: Tank resets can happen multiple times; only the last one matters for your actual start line.
• Performance Reality: O(n) time, O(1) space — unless you insist on console logging every step, then best of luck to your scroll wheel.

🧠 Interviewer Brain-Tattoo

“If you can’t pay your bills for the whole trip, it doesn’t matter where you start — you’re broke. Reset where you run dry and drive on. That’s greedy done right.”