LeetCode gas station implementation

Question

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique. Both input arrays are non-empty and have the same length. Each element in the input arrays is a non-negative integer. Example 1:

Input: gas = [1,2,3,4,5] cost = [3,4,5,1,2]

Output: 3

Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index. Example 2:

Input: gas = [2,3,4] cost = [3,4,3]

Output: -1

Explanation: You can't start at station 0 or 1, as there is not enough gas to travel to the next station. Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 0. Your tank = 4 - 3 + 2 = 3 Travel to station 1. Your tank = 3 - 3 + 3 = 3 You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3. Therefore, you can't travel around the circuit once no matter where you start.

Here is my solution:

public class Solution {
    public int CanCompleteCircuit(int[] gas, int[] cost) {
        int startIndex = 0;
        int tank = 0;
        int diff= 0;
        int sum =0;
        for(int i=0;i < gas.Length; i++)
        {
            diff = gas[i] - cost[i];
            sum += diff;
            if(tank + diff < 0)
            {
                startIndex = i+1;
                tank = 0;
            }
            else
            {
                tank += diff;
            }
        }
        if(sum < 0)
        {
            return -1;
        }
        else
        {
            return startIndex;
        }
    }
}

Please review code runtime and memory. Any other comments are welcome!

Answer 1

Your code nicely exploits all the constraints from the instructions.

It runs in linear time, which is much better than the naive approach, which would run in quadratic time.

It doesn't need any space other than a few local variables. Perfect.

Without further explanation the code is a bit hard to follow because of the many variables, and it is not entirely clear what sum and diff are exactly. Sure, sum holds a sum, but of what?

The diff variable should move inside the for loop since it is only needed there.

Instead of tank + diff < 0, you could also write tank < diff, but since you later compute tank + diff, having this common subexpression in the code is actually useful. You could also combine the expressions: just execute tank += diff, and if there's a negative amount of gas in the tank after that, reset it to zero. It's impossible in the real world to have negative amounts of gas in the tank, but it would make the code shorter.

For understanding the algorithm I would have preferred a variant that has two for loops. In the first loop, just compute the sum. In the second loop, determine the starting index. That way, there's fewer variables who can confuse me, the human reader. But if you're going for execution speed, you approach is perfect, again.

I would have preferred a short introduction about how you constructed your algorithm. Learning the ideas and then going from ideas to code is often easier than going backwards from the code to the underlying ideas.