Most Intuitive Solution, Did anybody post this idea before?


  • 1
    S

    Most Intuitive Solution, Did anybody post this idea before?
    The main idea is cut the circuit as two part. Let' s denote startas the index of start station, n as the #stations. Notice that for each start point, when back to the start , the car must goes through the station[n-1].
    The first path is start -> 0 , the second path is 0 -> start. During each part, if rest < 0, we continue by starting with next station. Here is the code.

    public static int canCompleteCircuit(int[] gas, int[] cost) {
            int n = gas.length;
            for (int start = 0; start < n; start++) {
                int rest = 0, i = start;
                // first part, from start -> 0
                for (;  i < n; i++) {
                    rest += gas[i];
                    rest -= cost[i];
                    if (rest < 0)   break;
                }
                if (i < n)  continue;   // gas is not enough in first part
                i = i % n;  // now our car is at station[0]
                for (; i < start; i++) {
                    rest += gas[i];
                    rest -= cost[i];
                    if (rest < 0)   break;
                }
                if (i < start)  continue;   //can't go through second part
                return start;
            }
            return -1;
        }

Log in to reply
 

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