Gas Station

3 min read
Greedy
LC-Medium

Oct 21, 2022

3 years ago

LeetCode

Solution

If the sum of gas is less than sum of cost, we know that we don't have enough gas to make the entire trip. So immediately return -1
We will be greedy here (for no apparent reason) and check each index one by one, starting from 0
Keep track of fuel at any given point. If fuel reaches 0, it means we cannot go further, so we reset fuel to 0 and start looking from the next index, because we are greedy:
- Here is where we also set ans to i + 1, because our question says that we are guaranteed a solution- and that solution will be unique
- If we ever reach a point where our fuel is 0, we need to consider the immediate next index, so we set start to i + 1
- If we reach the end of the array, we don't have to check the rest of the array that came before the start.
  - This is because we're guaranteed a unique solution exists, and if we're able to reach the end of the array from the current point i, it means we can reach the gas station from all other points from i + 1 to end
  - Since there can only be one answer, our current index must be the answer.
  - And since we already checked if we have enough gas to complete the whole thing using the line if sum(gas) < sum(cost), we know for a fact that we'll have enough fuel to complete the answer
- The answer is kinda intuitive / kinda not. I mean I can tell you that it'll work but I cannot give proper proof.
- Just keep these two points in mind:
  - There is a guaranteed unique solution.
  - If we can reach the end of the array from our start, we don't need to check the points before our start, because we know we have enough fuel, and we know the solution is unique.

Time	Space	Explanation
`O(n)`	`O(1)`

def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: if sum(gas) < sum(cost): return -1 fuel = 0 start = 0 for i in range(len(gas)): fuel += (gas[i] - cost[i]) if fuel < 0: fuel = 0 start = i + 1 return start