Leetcode.com problem 134: "Gas Station"

James S. Plank

Sun Jul 7 11:41:10 EDT 2019

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
A program that generates input problems (although it doesn't verify that solutions are unique).
Success Rate (as of July, 2019): 34.2%

This is an example of a problem that appears tricky, but as you think through it, and in my case visualize it, the solution falls out very easily.

In case Leetcode's servers are down

If Leetcode's servers are down, I've given you tools to do the problem anyway. Please see the Topcoder problem "Cryptography" for an example of how to program with this workflow, when servers are down.

Here is a summary of the problem:

You are to implement a class called Solution, which has a public method:

int canCompleteCircuit(vector<int>& gas, vector<int>& cost);

The two vectors are the same size, and they contain non-negative integers. They represent gas stations. You will start at a station s, with an empty tank of gas in your car. You will add gas[s] gallons of gas to your car, and then it will take cost[s] gallons of gas to get to the next station (station (s+1)%gas.size()). Your car holds an infinite amount of gas.

You should return the index of s, which is your starting station, if it is possible to visit every station, and return to s, without running out of gas. If there is no such station, return -1. The problems are such that if s exists, it is unique.

The examples

Example	Gas	Cost	Answer
1	{ 1, 2, 3, 4, 5 }	{ 3, 4, 5, 1, 2 }	3
2	{ 2, 3, 4 }	{ 3, 4, 3 }	-1

Hints

It's easy to write a slow solution to this problem. The solution goes like this: Write a method string starting_with_i(int i), which solves the following problem: given starting station i, can I travel around the circuit once without running out of gas? You do this by keeping track of the amount of gas that you have at every station, and if that amount ever goes below zero, you return "no". If you go all the way around the circuit, you return "yes".

Then, you can call starting_with_i() with every value of i, and answer the problem. I hope that you see that such a solution is O(n²), so it's unacceptable as n grows. And leetcode will give you large problems to make such a solution fail.

So, you can't test every starting position. However, suppose you call starting_with_i(0), and graph the amount of gas you have at every station, regardless of whether that amount goes negative. Do that by hand for example 1 above. Do you see how doing that gives you an O(n) solution to the problem?

If Leetcode's servers are working, go ahead and solve it there. Otherwise, you can test yourself with test.sh, and your output should be identical to answers.txt. Each test should take under a second, even that last one which has 510,000 stations!