My Python solution O(n) time O(1) space and not applying greedy beating 94%

  • 0

    I am going to start with an example:
    gas = [4,6,3,1,3]
    cost = [5,4,2,5,1]

    I came up with the following solution with this:
    Suppose the current index has gas less than cost, it certainly would not be the answer. (because we need that difference to be positive)

    Then suppose we start with a index which has positive difference, if we add the difference until a point the sum become negative, that means starting from that point and the following points will not be able to provide us with enough gas. So we have to abandon the indexes before the index where we hit negative sum.

    Also be careful since it's circular, that means we can take modulo of index if it exceeds our gas/cost array length.

    def canCompleteCircuit(self, gas, cost):
            :type gas: List[int]
            :type cost: List[int]
            :rtype: int
            if sum(gas) < sum(cost):
                return -1
            i = 0
            while i < len(gas):
                if gas[i] < cost[i]:
                    #certainly not what we look for
                    i += 1
                    j = i
                    sum_diff = gas[j] - cost[j]
                    j = (j + 1) % len(gas)
                    while j != i:
                        sum_diff += (gas[j] - cost[j])
                        if sum_diff < 0:
                            # sum becomes negative, we can safely abandon all the points before j
                            # (including j)
                            i = (j + 1) % len(gas)
                            j = (j + 1) % len(gas)
                    if sum_diff >= 0:
                        return j
            return -1

  • 0

Log in to reply

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