unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 134: Gas Station

link

Time: \mathcal{O}(n^2), space: \mathcal{O}(1).

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        def can_complete_circuit(gas: List[int], cost: List[int], start: int) -> bool:
            n = len(gas)
            current, left_over, required_hops = start, 0, n
            while required_hops > 0:
                current_gas = gas[current] + left_over
                required_gas = cost[current]
                if current_gas < required_gas:
                    return False
                left_over = current_gas - required_gas
                current = (current+1) % n
                required_hops -= 1
            return True

        return next((start for start in range(len(gas)) if can_complete_circuit(gas, cost, start)), -1)

For a gas station, the net (gas-cost) >= 0 means we can make it to the next station. Since sum does not depend on the order of the numbers being summed up (commutativity), this also holds for a sequence of gas stations. Therefore, the sum of the nets of a sequence of gas stations tell us if we could circuit through them.

Time: \mathcal{O}(n^2), space: \mathcal{O}(1).

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        def can_complete_circuit(gas: List[int], cost: List[int], start: int) -> bool:
            n = len(gas)
            current, left_over, required_hops = start, 0, n
            while required_hops > 0:
                current_gas = gas[current] + left_over
                required_gas = cost[current]
                if current_gas < required_gas:
                    return False
                left_over = current_gas - required_gas
                current = (current+1) % n
                required_hops -= 1
            return True

        net = sum( g-c for g, c in zip(gas, cost) )
        if net < 0:
            return -1
        
        return next((start for start in range(len(gas)) if can_complete_circuit(gas, cost, start)), -1)

To improve, we can try the starting gas stations from bigger to smaller nets.

Time: \mathcal{O}(n^2), space: \mathcal{O}(1).

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        def can_complete_circuit(gas: List[int], cost: List[int], start: int) -> bool:
            n = len(gas)
            current, left_over, required_hops = start, 0, n
            while required_hops > 0:
                current_gas = gas[current] + left_over
                required_gas = cost[current]
                if current_gas < required_gas:
                    return False
                left_over = current_gas - required_gas
                current = (current+1) % n
                required_hops -= 1
            return True

        net = sum( g-c for g, c in zip(gas, cost) )
        if net < 0:
            return -1
        
        n = len(gas)
        ordered_starts = sorted(list(range(n)), key=lambda i: gas[i]-cost[i], reverse=True)

        return next((start for start in ordered_starts if can_complete_circuit(gas, cost, start)), -1)

If net (gas-cost) of a station is negative, we might be able to boost its net by starting at an earlier station. Because, if the earlier station had a positive net, that trickles down to the current station as left_over. In this way we need to traverse the stations once.

Time: \mathcal{O}(n), space: \mathcal{O}(1)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        station_net = lambda i, left_over: gas[i]-cost[i]+left_over        
        n = len(gas)
        current_station, begin_station, left_over_gas = 0, 0, 0

        # If there isn't a solution, the begin_station ends up right next
        # to the current_station. However, the current_station's net being
        # negative, it cannot move forward to meet the begin_station.
        while (next_station := (current_station+1) % n) != begin_station:
            current_station_net = station_net(current_station, left_over_gas)
            if current_station_net >= 0:
                current_station = next_station
                left_over_gas = current_station_net
            else:
                begin_station = (begin_station - 1) % n
                left_over_gas += gas[begin_station]-cost[begin_station]

        # Can we make the last hop back to the begin_station?
        return begin_station if station_net(current_station, left_over_gas) >= 0 else -1

tanvirdotzaman

Leave a comment