Super simple solution in Java, runs within 200ms


  • 0
    C
    public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int n = gas.length;
            int l = 0;
            int r = 1 % n;
            int sum = gas[l] - cost[l];
            while(l < n && l != r) {
                if (sum < 0) {
                    sum -= gas[l] - cost[l];
                    l++;
                    if (l != r) continue;
                }
                sum += gas[r] - cost[r];
                r = (r + 1) % n;
            }
            
            if (l == n || sum < 0) return -1;
            return l;
        }
    }
    

    The basic idea is that we put two pointer l and r on the array and maintains the sum of gas[i] - cost[i] from l to r (in a recurring way for r but not l), once we found an l that enables r to travel to the same position of l without sum < 0 at any single step, we know l now is the solution of the problem.

    Otherwise, If at last l travels to n, we have already tried every index and no one can make r travels back, there is no solution for this problem. Same result when the sum at last is negative.

    l moves at most n steps, r moves at most 2 * n times, so the time complexity is O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.