Gas Station — LeetCode (Explanation: Why Greedy?)

Question:

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

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

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

I will discuss the solution later, but first who understand it already and are stuck on part that why this problem is greedy or why the loop goes only till gas.length is what I am going to explain here

Let’s take the same example

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

Brain teaser1: Why we choose i=3 and not i=4, with greedy approach

Brain teaser2: So why this line of code and not to complete the full circle when i=3 and just end at gas.length

for(let i=0;i<gas.length;i++)

Brain Teaser 1:

1. So we are at i=3, at this point this is clear that solution can be i=3rd or i=4th(last index)
2. Let assume if i=4 is solution, and we can see we can reach from i=3 to i=4, then 3 should also be the solution
3. But the condition is already given in question, that their is 1 unique solution
4. So if it must be only i=3 which will be solution, as if we are also considering i=4 and we can also see that we can travel from 3 to 4, then there are 2 solution, so that’s why we choose 3.

Brain teaser2:

1. Why not go full loop, and end at gas.length
2. The reason is when we are at i=4 (last index), we have the total difference= Σgas-Σcost
3. If this is postive at i=4, it means that we can traverse the rest and no need to lopp again till start Index-1

So these are the two important points in this question, which decreases the time complexity much

Here’s the solution

var canCompleteCircuit = function(gas, cost) {
    let totalDiff=0
    let n = gas.length
    fuel=0
    index=0
    for(let i=0;i<n;i++){
        let diff = gas[i] - cost[i]
        totalDiff= totalDiff + diff
        fuel = fuel + diff
        if(fuel<0){
            fuel=0
            index=i+1
            continue
        }
    }

    return totalDiff<0? -1 : index
};