Gas Station Circuit

You're tasked with finding if a circular route connecting several gas stations is possible, given the amount of gas available at each station and the cost to travel to the next station. This is a classic problem that tests your ability to manage resources and find a valid starting point in a cyclical system.

Problem Description

You are given two arrays, gas and cost, of equal length. gas[i] represents the amount of gas available at the i-th gas station. cost[i] represents the amount of gas required to travel from the i-th gas station to the (i+1)-th gas station. The last station connects back to the first station (i.e., from station n-1 to station 0).

Your goal is to find a starting gas station index from which you can complete a full circuit. You start with an empty tank. If there are multiple possible starting stations, return any one of them. If no such station exists, return -1.

Key Requirements:

• You must be able to travel from your starting station, visit all other stations in order, and return to your starting station.
• At any point during the journey, your gas tank cannot be negative.

Expected Behavior:

• If a valid starting station is found, return its index (0-based).
• If no valid starting station exists, return -1.

Edge Cases to Consider:

• What if there's only one gas station?
• What if the total gas available is less than the total cost required for the entire circuit?

Examples

Example 1:

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

Output: 3
Explanation:
Starting at station 3 (index 3):
- Tank: 0. At station 3, get 4 gas. Tank = 4. Travel to station 4, cost 1. Tank = 3.
- At station 4, get 5 gas. Tank = 3 + 5 = 8. Travel to station 0, cost 2. Tank = 6.
- At station 0, get 1 gas. Tank = 6 + 1 = 7. Travel to station 1, cost 3. Tank = 4.
- At station 1, get 2 gas. Tank = 4 + 2 = 6. Travel to station 2, cost 4. Tank = 2.
- At station 2, get 3 gas. Tank = 2 + 3 = 5. Travel to station 3, cost 5. Tank = 0.
Circuit completed successfully.

Example 2:

Input:
gas = [2, 3, 4]
cost = [3, 4, 3]

Output: -1
Explanation:
Let's try starting at each station:
- Start at 0: gas=2, cost=3. Initial tank: 2. Travel to 1, cost 3. Tank becomes 2-3 = -1. Fails.
- Start at 1: gas=3, cost=4. Initial tank: 3. Travel to 2, cost 4. Tank becomes 3-4 = -1. Fails.
- Start at 2: gas=4, cost=3. Initial tank: 4. Travel to 0, cost 3. Tank becomes 4-3 = 1. At station 0, gas=2. Tank becomes 1+2=3. Travel to 1, cost 3. Tank becomes 3-3=0. At station 1, gas=3. Tank becomes 0+3=3. Travel to 2, cost 4. Tank becomes 3-4 = -1. Fails.
No starting station allows completing the circuit.

Example 3: (Edge Case: Single Station)

Input:
gas = [5]
cost = [5]

Output: 0
Explanation:
Starting at station 0:
- Tank: 0. At station 0, get 5 gas. Tank = 5. Travel to station 0, cost 5. Tank = 0.
Circuit completed successfully.

Constraints

• 1 <= gas.length == cost.length <= 10^5
• 0 <= gas[i], cost[i] <= 10^4
• The total gas sum(gas) may be greater than or equal to the total cost sum(cost). If sum(gas) < sum(cost), it's impossible to complete the circuit.
• Your algorithm should aim for an efficient time complexity, ideally O(N), where N is the number of gas stations.

Notes

• Remember that you start with an empty gas tank.
• The problem guarantees that if a solution exists, it is unique. However, this is a common misinterpretation. The problem asks to return any one valid starting point if multiple exist. The uniqueness guarantee is often made in slightly different variations. For this problem, assume there might be multiple valid starting points, and you just need to find one.
• Consider what happens if you run out of gas exactly when you reach the next station. This is still considered a valid step. You must have non-negative gas before traveling to the next station.