Reference: LeetCode EPI 17.6

Difficulty: Medium

My Post: Java B-F/Greedy Solutions with Explanation, Comments and Illustration (easy-understand)

## Problem

There are

`N`

gas stations along a circular route, where the amount of gas at station`i`

is`gas[i]`

.

You have a car with an unlimited gas tank and it costs

`cost[i]`

of gas to travel from station`i`

to its next station`(i + 1)`

. You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return `-1`

.

**Note:**

- If there exists a solution, it is guaranteed to be unique.
- Both input arrays are non-empty and have the same length.
- Each element in the input arrays is a non-negative integer.

**Example:**

1 | gas = [1,2,3,4,5] |

## Analysis

### Brute-Force

The idea of brute-force is to examine each single station (or city in EPI book):

- Choose the station as a starting point.
- Simulate the road trip to see if the following stations are reachable.

**Note:** See comments.

1 | public int canCompleteCircuit(int[] gas, int[] cost) { |

**Time:** $O(N^2)$**Space:** $O(1)$

### Greedy

Proof by Contradiction: LeetCode Solution (if you have time)

The illustration in the EPI book helps understand the algorithm.

**Note:** The problem statement is a bit different, but the idea is the same. (`Distance`

equals `Gas Cost`

, `City`

equals `Station`

)

We can see that at `D`

we have the **lowest gallon** before refueling (negative gallon is allowed in the algorithm). Now take the station `D`

as the starting point then we can have the optimal solution (if it exists).

At last, check the starting point at last to see if such an `ample`

station exists. If the gallon at last is negative which means we don’t have enough gallons in total to do the road trip (return `-1`

).

**Note:** See comments.

1 | public int canCompleteCircuit(int[] gas, int[] cost) { |

**Time:** $O(N)$**Space:** $O(1)$