Change the problem into largest sum contiguous subarray


  • 2
    J

    My thought is to change the problem into largest sum contiguous subarray.
    If sum(gas) - sum(cost) < 0, then return -1.
    Else return the start index of largest sum contiguous subarray of [gas[i] - cost[i] for i in range(len(gas))].

    def canCompleteCircuit(self, gas, cost):
        if len(gas) == 0:
            return -1
        if sum(gas) - sum(cost) < 0:
            return -1
    
        return self.get_largest_sum_index([gas[i] - cost[i] for i in range(len(gas))])
    
    def get_largest_sum_index(self, l):
        sum = -1
        index = -1
        for i in xrange(len(l)):
            sum_l = sum + l[i]
            if l[i] > sum_l:
                sum = l[i]
                index = i
            else:
                sum = sum_l
        if sum < 0:
            return -1
        return index

Log in to reply
 

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