O(n) time, O(1) space, beat 98%


  • 0
    Y
    class Solution(object):
        def canCompleteCircuit(self, gas, cost):
            start,end, count = 0, 0, 1
            total = gas[start] - cost[start]
            while count < len(gas):
                if total >= 0:
                    start = (start + 1)%len(gas)
                    total += gas[start] - cost[start]
                else:
                    end -= 1
                    if end < 0:
                        end = end + len(gas)
                    total += gas[end] - cost[end]
                count += 1
            if total >= 0 and gas[end] - cost[end] >= 0:
                return end
            return -1
    

Log in to reply
 

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