My O(N) time, O(1) extra space solution.


  • 24
    H
    public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for(int i = 0; i < gas.length; i++) {
            gas[i] -= cost[i];
        }
        int sum = 0;
        int result = 0;
        int n = gas.length;
        for(int i = 0; i < n * 2 - 1; i++) {
            sum += gas[i % n];
            if(sum < 0) {
                result = i + 1;
                if(result >= n) {
                    return -1;
                }
                sum = 0;
            }
        }
        return result;
    }

  • 2
    A

    What does "i < n * 2 - 1" mean?


  • 0
    H

    We have to check every node (station) to see if it meets the criteria and we can't stop at n - 1 cause there's possibility that no station is satisfied. So when we come to the n - 1 node, we have to go another round.


  • 0

    Simulate a cycle by an array, such as:
    0,1,2...n-1,0,1,2....n-2
    total 2n-1 elements.


  • 3
    Y

    Why are you so smart?


  • 0
    N

    Does this also count leftover gas? Say, at station i, we have 2 units extra gas, which comes in handy at station i+1, where we fall 1 unit of gas short. Does this come under the purview of the question, and if yes, I'm not sure where this is accounted for in the code


  • 0
    N

    Sorry. My bad. I made a mistake in reading the code. I understand now.


Log in to reply
 

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