O(n) time + constant space solution. Two pointers.


  • 1
    L

    Algo: Two pointers. One points to a range's start, and the other points to the range's end. If the range is valid, move end pointer to next, otherwise move start pointer to next.
    Time: O(n)
    Space: Constant

    In code, "s" is the start pointer and "t" is the end pointer. "sum", which is a accumulation of remain gas, is used for range validation.

    class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    		int n = gas.size();
    		int s = 0;
    		int t = 0;
    		int sum = 0;
    		while (s < n) {
    			while (t - s <= n) {
    				sum += gas[t%n] - cost[t%n];
    				if (sum < 0)
    					break;
    				++t;
    			}
    			if (t - s > n)
    				return s;
    			while (s <= t) {
    				sum += -gas[s] + cost[s];
    				++s;
    				if (sum >= 0)
    					break;
    			}
    			if (t < s) {
    				sum = 0;
    				t = s;
    			}
    		}
    		return -1;
        }
    };

  • 0
    N

    Time complexity is O(n^2)


Log in to reply
 

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