Golang concise O(N) solution


  • 0

    If we first start from gas[0] and failed at gas[n] , we can skip retrying to start from gas[1]gas[n-1] th index.
    This can be proved like: let's say we can go through from gas[1] to gas[n] while we failed from gas[0] to gas[n] , this happens only the cost to gas[0] to gas[1] is minus...but then we should have failed from gas[0] to gas[1] at the first trial, which contradicts the fact.

    So when we chose the start point, we can ignore the point in the middle between the start and the failed index. We need to just try going through len(gas) distance from the start point we chose in this manner.

    func canCompleteCircuit(gas []int, cost []int) int {
    	glen := len(gas)
    	var start, amount int
    LOOP:
    	// loop to set a new start point
    	for i := 0; i < glen; {
    		start, amount = i, 0
    		// loop to check if we can complete a cycle from start to end
    		for j := 0; j < glen; j++ {
    			cur := (start + j) % glen
    			if amount = amount + gas[cur] - cost[cur]; amount < 0 {
    				if i+j >= glen {
    					return -1 // all start points failed
    				}
    				i += j + 1 // skip the start point
    				continue LOOP
    			}
    		}
    		return start
    	}
    	return -1
    }
    

    The worst scenario is all gas[i] - cost[i] < 0 but even in this case, we can just chose each point as a start index, so still O(N) while N is the length of gas.


Log in to reply
 

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