Python solution: O(n) runtime and main idea


  • 1
    A

    main idea: sum(gas[i] - cost[i]) is non-negative if solution exists. If solution exists, then a guaranteed valid starting point is index such that the cumulative sum of gas[i] - cost[i] values are at minimum.

    note: the %len(gas) at the return statement is actually not required but its there for clarity.

    class Solution(object):
        def canCompleteCircuit(self, gas, cost):
            """
            :type gas: List[int]
            :type cost: List[int]
            :rtype: int
            """
            min_ind = 0
            min_val = 0
            val = 0
            for i in xrange(len(gas)):
                val += gas[i] - cost[i]
                if val < min_val:
                    min_ind = i + 1
                    min_val = val
            if val < 0:
                return -1
            return min_ind % len(gas)
    

  • 0
    W

    Thank you so much for sharing your code.

    Could you please elaborate on why "If solution exists, then a guaranteed valid starting point is index such that the cumulative sum of gas[i] - cost[i] values are at minimum."

    Appreciate it.


  • 0
    A

    Try plotting out the cumulative sum array of the gas[i] - cost[i] values, for various possible inputs. You'll notice that the total sum at the end is always the same, but how it gets there can change depending on where you start. Also notice that some trajectories of this cumsum can dip negative, in those cases, if you shift the array to that minimum point, you are guaranteed a path that always stays positive.. Hope that's clear.


Log in to reply
 

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