Got TLE on Python solution, is there a faster one?


  • 0
    G

    Here's my code:

    class Solution:
        # @param gas, a list of integers
        # @param cost, a list of integers
        # @return an integer
        def canCompleteCircuit(self, gas, cost):
            if len(gas) < 1:
                return -1
            for i in range(len(gas)):
                count = 0
                gas_total = 0
                cost_total = 0
                station = i
                while count < len(gas):
                    gas_total += gas[station]
                    cost_total += cost[station]
                    if station == len(gas)-1:
                        station = 0
                    else:
                        station += 1
                    if gas_total < cost_total:
                        break
                    else:
                        count += 1
                if gas_total >= cost_total:
                    return i
                else:
                    continue
            return -1
    

    Not the prettiest but it's the only way I can think of to express the logic that one should start at each station and keep a cumulative count of the gas obtained and expended, and that if at any point more gas has been expended than obtained, break out of the circuit and start over at the next station.

    Is there a better (faster) way to express this logic? Or perhaps a simpler bit of logic to solve the problem altogether?


  • 6
    M

    Your algorithm has a time cost of O(n^2), which is not necessary.

    A better strategy (with O(n) cost) to tackle this problem is:

    1. start from whatever station, complete the circle pretending you
      car can still keep going with negative gas.

    2. record the station at which your car has the lowest level of gas. ( that is the station
      with the best chance to finish the circle).

    3. record the final gas level when the circle is finished. if it is negative (means sum(gas) < sum(cost)), then no solution is possible.

      My code is attached :

      class Solution:
          # @param gas, a list of integers
          # @param cost, a list of integers
          # @return an integer
          def canCompleteCircuit(self, gas, cost):
      
                left = 0
                lowlevel = 0
                minindex = 0  
                
                n = len(gas)
                
                for i in range(n):
                    left += gas[i] 
                    left -= cost[i]
                    
                    if (left<lowlevel):
                        lowlevel = left
                        minindex = (i+1) % n
                
                if left <0 :
                    return -1
                
                return minindex
    

Log in to reply
 

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