Intuition

Find the first station where we have a net positive tank.

However that solution is not optimized.

Approach

After reading the editorial, it’s possible to complete the solution with optimal time complexity using the greedy approach (one pass).

The idea is to go iterate over the elements and whenever we find a net negative level we restart the segment and keep the next array index as starting index. Also, while going over the elements we need to keep a the final tank level. If the final tank level is negative, then there’s no solution.

Complexity

• Time complexity: O(n)
  • we read the array just one time, since O(n)
• Space complexity: O(1)
  • only control variables

Code

class Solution(object):
    memo = []
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        total_gain = 0
        curr_gain = 0
        answer = 0

        for i in range(len(gas)):
            total_gain += gas[i] - cost[i]
            curr_gain += gas[i] - cost[i]
            if curr_gain < 0:
                answer = i+1
                curr_gain = 0

        return -1 if total_gain < 0 else answer