Solutions

# Brute force, greedy or 2 pointers. Greedy: keep track of gas balance, if it becomes negative we can't start from any of the preceding stations, so we move the start pointer to the next station and reset the balance. 2 pointers: one from the end and one from the start, move the end pointer until we run out of gas, then move the start pointer until we have gas again, repeat until they meet. 
# greedy

# Greedy (sort of Kadane's algorithm applied to gas[i]-cost[i] array) - O(n) time, O(1) space
def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
    if sum(gas) < sum(cost):
        return -1
    # else: we know there is one (only one) solution

    tank = 0 # gas balance
    start_i = 0
    for i in range(len(gas)):
        tank += (gas[i] - cost[i])
        if tank < 0:
            tank = 0
            start_i = (i + 1) % len(gas)
    # we don't need to loop back from the beginning
    # because we know that only 1 solution exists, so it must be it
    # as we already excluded all the preceding positions

    return start_i

"""By visualizing this process, we can see that it involves dividing our journey
into segments, each of which ends in a "valley" station where the accumulated gas becomes negative.
These segments cannot be crossed with 0 initial gas, and any station within them is not a valid starting station.

By design: acc_gas_seg1 + acc_gas_seg2 + acc_gas_seg3 >= 0
So if acc_gas_seg1 and acc_gas_seg2 are negative, acc_gas_se3 will be positive
and will allow to finish the circle, so we don't need to loop the circle back from the beginning.
"""

# 2 pointers - O(n) time, O(1) space
def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
    n = len(gas)
    # 2 pointers:
    # - start: from the end goes towards start <---
    # - end: from start goes towards end --->
    start, end = n - 1, 0
    tank = gas[start] - cost[start]
    while start > end:
        if tank < 0:
            start -= 1
            tank += gas[start] - cost[start]
        else:
            tank += gas[end] - cost[end]
            end += 1
    return start if tank >= 0 else -1
    
# Brute force - O(n^2) time, O(1) space
def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
    n = len(gas)

    for i in range(len(gas)):
        tank = gas[i] - cost[i]
        if tank < 0:
            continue

        j = (i + 1) % n
        while j != i:
            tank += (gas[j] - cost[j])
            if tank < 0:
                break

            j = (j+1) % n

        if j == i:
            return i

    return -1