Gas Station - Miscellaneous / Greedy

Problems
1

https://algo.monster/problems/gas_station

2

another way to solve this that might make this easier:
class Solution(object):
def canCompleteCircuit(self, gas, cost):
“”"
:type gas: List[int]
:type cost: List[int]
:rtype: int
“”"
rems = [gas[i]-cost[i] for i in range(len(gas))]
if sum(rems)<0:
return -1
else:
currentSum = 0
start = 0
for i, rem in enumerate(rems):
currentSum+=rem
if currentSum<0:
start = i+1
currentSum = 0

    return start
3

We just want to start at the first station that will give you max leftover gas when arriving the next (this is how greedy works). So just need one round of loop and 3 integers to track: 1) total left over, for the circle it must be >=0; 2) max local leftover value and 3) max local leftover index.

5

Another way to solve this in a single loop is to keep track of both the currentGas left and the totalGas used in the entire round trip. Basically if the totalGas needed to complete the trip is greater than 0 after accounting for the total distance traveled, there must be a solution. To get that solution, you try to find the a station such that starting from that station, it’ll cover whatever gas deficit you’ve seen so far.

function startingStation(gas, dist) {
    const n = gas.length;
    let start = null;
    let currentGas = 0, currentLoc = 0;
    while (currentLoc < n * 2) {
        if (start == null) {
            start = currentLoc;
        }
        currentGas += gas[currentLoc % n];
        currentGas -= dist[currentLoc % n];
        if (currentGas < 0) {
            start = null;
            currentGas = 0;
        }
        currentLoc += 1;
        if (start != null && currentLoc - start === n) {
            return start % n;
        }
    }
    return -1;
}
6

Structured Programming JS Solution

function startingStation(gas, dist) {
    const n = gas.length;
    
    let currentGas = 0;
    let currentLoc = 0;
    let start = 0;
    let result = -1;
   
    while (currentLoc < n * 2 && result === -1) {
        const mod = currentLoc % n;
        
        currentGas += gas[mod] - dist[mod];
        currentLoc += 1;
        
        if (currentGas < 0) {
            start = currentLoc
            currentGas = 0;
        } else if (currentLoc - start === n) {
           result = start % n; 
        }
    }
    
    return result;
}
7

this video is nice in explaining why the next starting point should be if a gas station fails https://www.youtube.com/watch?v=wDgKaNrSOEI