class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 1 2 3 4 5 1 2 3 4 5
        // 3 4 5 1 2 3 4 5 1 2

        // 2 3 4 2 3 4
        // 3 4 3 3 4 3
        int n = gas.length;
        int[] circleGas = new int[n*2];
        int[] circleCost = new int[n*2];

        for(int i = 0; i < n; i++) {
            circleGas[i] = gas[i];
            circleGas[i + n] = gas[i];
            circleCost[i] = cost[i];
            circleCost[i + n] = cost[i];
        }
        
        for(int i = 0; i < n; i++) {
            if(gas[i] >= cost[i]) {
                // start checking
                int gasSum = gas[i];
                int costSum = cost[i];
                boolean isFailed = false;
                
                for(int j = i+1; j < i + n; j++) {
                    gasSum += circleGas[j];
                    costSum += circleCost[j];
                    if(costSum > gasSum) {
                        // failed
                        isFailed = true;
                        break;
                    }
                }
                if(!isFailed) return i;
            }
        }
        return -1;
    }
}