134. Gas Station (Leetcode) (optimized + unoptimized)

// class Solution {
//     public int canCompleteCircuit(int[] gas, int[] cost) {
//         int volumeOfGas = 0;

//         for(int i = 0; i < gas.length; i++) {
//             volumeOfGas = gas[i];
//             for(int j = ( i + gas.length + 1) % gas.length, count = 0, counter = ( i + gas.length + 1) % gas.length; count < gas.length; count++) {
//                 volumeOfGas = (volumeOfGas - cost[j]) + gas[j];
//                 if(volumeOfGas < 0) break;
//                 if(j == counter) return i;
//             }
//         }

//         return -1;
//     }
// }

// class Solution {
//     public int canCompleteCircuit(int[] gas, int[] cost) {
//         int n = gas.length;

//         for (int i = 0; i < n; i++) {
//             int start = i;
//             int gasLeft = 0;

//             while (gasLeft >= 0) {
//                 gasLeft = gasLeft + gas[start] - cost[start];
//                 start = (start + 1) % n;

//                 if (start == i && gasLeft >= 0) {
//                     return i;
//                 }
//             }
//         }

//         return -1;
//     }
// }

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int currentGas = 0;
        int start = 0;
        
        for (int i = 0; i < gas.length; i++) {
            totalGas = totalGas + gas[i] - cost[i];
            currentGas = currentGas + gas[i] - cost[i];
            
            if (currentGas < 0) {
                start = i + 1;
                currentGas = 0;
            }
        }
        
        return totalGas >= 0 ? start : -1;
    }
}