The Gas Station problem (can you drive around a circular route given gas[i] and cost[i]?) is short to code, but interviewers mostly grade whether you can justify the greedy step.
Try every starting station and simulate the loop: O(n^2). Say it, then improve it.
So when the tank goes negative at j, jump the candidate start to j + 1 and reset the tank.
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1
start, tank = 0, 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1
tank = 0
return start
If the totals are non-negative, a solution exists, and the last reset point is the only place from which the tank never dips below zero through the end of the array; the surplus from the total covers the wrap-around part.
O(n) time, O(1) space.
State fact 2 out loud before coding. It turns "I just reset when negative" into a proof the interviewer can follow.
If you want to rehearse explaining proofs like this under time pressure, Linkjob AI coding interview copilot can help. Disclosure: I work on Linkjob AI.
Further reading: Linkjob AI resource directory