Gas Station

Leetcode Problem – Gas Station

---

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

---

Code C++

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int nGasSt = gas.size(), checkRoute = 0;
        vector<int> gapFuel;

        // Calculate gap fuel and total gap fuel
        for(int i = 0; i < nGasSt; i++) {
            gapFuel.push_back(gas[i]-cost[i]);
            checkRoute += gas[i]-cost[i];
        }

        // If there isn't enough gas to complete the route, return -1
        if(checkRoute < 0) return -1;

        // Set up two pointers and sum variable to simulate the circular route
        // frP => forward pointer, baP => backward pointer
        int frP = 0, baP = nGasSt-1, sum = 0;

        // Loop until the two pointers meet
        while(frP < baP) {
            // Add gap fuel of current gas station to sum
            sum += gapFuel[frP];

            // If sum becomes negative, starting gas station cannot be from 0 to frP
            if(sum < 0) {
                // Move the baP pointer backwards while subtracting gap fuel
                while(frP < baP && sum < 0) {
                    sum += gapFuel[baP];
                    baP--;
                }
            }

            // Move the frP pointer forward
            frP++;
        }

        // Return the starting index of gas station that can complete the circular route
        // Wrap back to 0 if baP+1 exceeds nGasSt
        return (baP+1)%nGasSt;

    }
};

---

Code Golang

func canCompleteCircuit(gas []int, cost []int) int {
    nGasSt := len(gas)
    var checkRoute int
    var gapFuel []int

    // Calculate gap fuel and total gap fuel
    for i := 0; i < nGasSt; i++ {
        gapFuel = append(gapFuel, gas[i]-cost[i])
        checkRoute += gas[i]-cost[i]
    }

    // If there isn't enough gas to complete the route, return -1
    if checkRoute < 0 {
        return -1
    }

    // Set up two pointers and sum variable to simulate the circular route
    // frP => forward pointer, baP => backward pointer
    frP, baP, sum := 0, nGasSt-1, 0

    // Loop until the two pointers meet
    for frP < baP {
        // Add gap fuel of current gas station to sum
        sum += gapFuel[frP]

        // If sum becomes negative, starting gas station cannot be from 0 to frP
        if sum < 0 {
            // Move the baP pointer backwards while subtracting gap fuel
            for frP < baP && sum < 0 {
                sum += gapFuel[baP]
                baP--
            }
        }

        // Move the frP pointer forward
        frP++
    }

    // Return the starting index of gas station that can complete the circular route
    // Wrap back to 0 if baP+1 exceeds nGasSt
    return (baP+1)%nGasSt
}

---

Code JAVA

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int nGasSt = gas.length, checkRoute = 0;
        int[] gapFuel = new int[nGasSt];

        // Calculate gap fuel and total gap fuel
        for (int i = 0; i < nGasSt; i++) {
            gapFuel[i] = gas[i] - cost[i];
            checkRoute += gapFuel[i];
        }

        // If there isn't enough gas to complete the route, return -1
        if (checkRoute < 0) {
            return -1;
        }

        // Set up two pointers and sum variable to simulate the circular route
        // frP => forward pointer, baP => backward pointer
        int frP = 0, baP = nGasSt - 1, sum = 0;

        // Loop until the two pointers meet
        while (frP < baP) {
            // Add gap fuel of current gas station to sum
            sum += gapFuel[frP];

            // If sum becomes negative, starting gas station cannot be from 0 to frP
            if (sum < 0) {
                // Move the baP pointer backwards while subtracting gap fuel
                while (frP < baP && sum < 0) {
                    sum += gapFuel[baP];
                    baP--;
                }
            }

            // Move the frP pointer forward
            frP++;
        }

        // Return the starting index of gas station that can complete the circular route
        // Wrap back to 0 if baP+1 exceeds nGasSt
        return (baP + 1) % nGasSt;
    }
}

---

Explanation

The code first computes the gap fuel, which is the difference between the amount of gas available and the amount of gas required to travel from one station to the next. The variable checkRoute is initialized as the sum of all the gap fuel, and if it is negative, it means that there is not enough gas to complete the route, so the function returns -1.

The function then uses two pointers frP and baP to simulate the circular route. frP points to the current gas station, and baP points to the gas station behind frP. The variable sum is used to track the total gap fuel from the starting gas station up to the current gas station frP. If sum becomes negative, it means that the starting gas station cannot be the one from 0 to frP. In this case, the code moves the pointer baP towards the end of the circular route while subtracting the gap fuel of the gas station pointed by baP from the sum. The loop continues until sum becomes non-negative or baP reaches frP.

Finally, the function returns the starting index baP+1 of the gas station that can be used to travel through all other gas stations in a circular route. If baP+1 is equal to nGasSt, which is the number of gas stations, the code uses the modulo operator % to wrap it back to 0.