Share my simple o(n) solution


  • 4
    V

    My idea is simple, try to travel 2 rounds. We set the start at the 0 at the begin.If we can not move to the next station, we reset the start as the next station. If we can move to the next station and find that next station is our start, we return next position.

    I also try to go backward and the result is same cause test data is not very strong. for example, gas(1, 2), cost(2, 1), we can not go forward, but we can go backward. The problem should clarify that whether we can go backward or not.

    class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
            int n = gas.size(), gas_amount = 0, start = 0;
            for (int i = 0; i < n * 2; ++i){
                int c = i % n, next = (c + 1) % n;
                if (gas_amount + gas[c] - cost[c] >= 0){
                    gas_amount = gas_amount + gas[c] - cost[c];
                    if (next == start)
                        return start;
                }
                else {
                    gas_amount = 0;
                    start = next;
                }
            }
            return -1;
        }
    };

  • 0
    V

    The problem doesn't specify you can go backward, so you can not.

    But...

    If you cannot move forward, you can add the station BEFORE the one you started from, and see if that helps.


Log in to reply
 

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