Three Clever Ways to Solve the Circular Gas Station Problem

Problem Statement

Given N gas stations on a circular route, array oil records the amount of fuel each station provides and array cost records the fuel needed to travel to the next station. Starting with an empty tank, determine if there exists a starting station index that allows completing a full circle; return the index or -1.

Key Points

Each station can refuel, and travel consumes fuel.

If consumption exceeds current fuel, the route is unreachable.

Any station can be a starting point.

If multiple solutions exist, any valid index is acceptable.

Example

Input: oil = [4,5,3,1,4,3] , cost = [5,4,3,4,2,1]

Output: 4

The car’s fuel level at each step is illustrated in the following diagram:

Solution Approaches

1. Brute‑Force Method

Test each station as a starting point. This straightforward approach runs in O(N²) time and serves as a baseline for optimization.

2. Reverse (Backtrack) Method

Iterate forward; when fuel becomes negative, “borrow” fuel by moving the start backward to the previous station. Continue until a feasible start is found or the whole circle is proven impossible.

Illustrations of the backtrack process are shown below:

3. Graphical (Cumulative‑Sum) Method

Plot the cumulative fuel balance versus station index. If the total balance is non‑negative, the lowest point of the curve indicates a valid starting station.

Conclusion

The brute‑force method is simple but inefficient, the reverse method offers a linear‑time greedy solution, and the graphical method provides an intuitive view of why a solution exists when total fuel is sufficient.