1. Problem Summary

You are given two integer arrays:

• gas[i] — the amount of fuel available at station i
• cost[i] — the fuel required to travel from station i to station (i + 1)

Stations form a circular route, meaning after the last station, you return to station 0.

Your task is to:

• determine if it is possible to complete the full circuit
• if possible, return the starting station index
• if not possible, return -1

Important constraints:

• You start with an empty tank.
• You can refuel only at the station you arrive at.
• You must maintain non-negative fuel throughout the journey.

---

2. Key Insights

Total fuel vs total cost determines feasibility

If the total gas available is less than the total cost required:

sum(gas) < sum(cost)  → impossible

If a starting point fails, all stations before it are invalid

When fuel becomes negative at index i, it means:

• no station from current start up to i can be a valid start
• so reset start to i + 1
• reset current fuel to 0

Only one valid starting index can exist

If a valid solution exists, it is guaranteed to be unique.

Greedy approach works

No need for brute force. A single pass is enough.

---

3. Approach

Greedy Linear Scan

Variables maintained:

• totalFuel — net fuel across full route
• currentFuel — running fuel starting from candidate station
• startIndex — current candidate start

Algorithm steps:

1. Initialize totals and starting index.
2. Loop through all stations:
   • accumulate totalFuel += gas[i] - cost[i]
   • accumulate currentFuel += gas[i] - cost[i]
3. If currentFuel becomes negative:
   • current start fails
   • set startIndex = i + 1
   • reset currentFuel = 0
4. After loop:
   • if totalFuel >= 0, return startIndex
   • else return -1

---

4. Time and Space Complexity

Time Complexity: O(N)

Only one traversal of stations.

Space Complexity: O(1)

No extra storage besides a few variables.

---

5. Java Solution

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalFuel = 0;
        int currentFuel = 0;
        int startIndex = 0;

        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            totalFuel += diff;
            currentFuel += diff;

            if (currentFuel < 0) {
                startIndex = i + 1;
                currentFuel = 0;
            }
        }

        return totalFuel >= 0 ? startIndex : -1;
    }
}

---

6. Dry Run Examples

Example 1

Input:

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

Step-by-step fuel differences:

i=0: diff = -2 → currentFuel = -2 → reset start to 1
i=1: diff = -2 → currentFuel = -2 → reset start to 2
i=2: diff = -2 → currentFuel = -2 → reset start to 3
i=3: diff = 3  → currentFuel = 3
i=4: diff = 3  → currentFuel = 6

totalFuel = (sum of diffs) = positive → valid

Final answer:

startIndex = 3

---

Example 2

Input:

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

Deltas:

-1, -1, 1 → totalFuel = -1

Since totalFuel < 0:

Final answer:

-1

---

Example 3

Input:

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

Deltas:

1, -3, 1, -2, 3

Running simulation:

• start at 0, fuel goes negative at i=1 → reset to 2
• from index 2 onward fuel stays non-negative
• totalFuel positive

Answer:

2

---

7. Why This Solution Works

• Greedy reset ensures only valid starting candidates remain
• Total fuel check ensures full circuit feasibility
• Avoids unnecessary recomputation
• Matches proven mathematical reasoning
• Guarantees correctness with O(N) performance

---

8. Common Mistakes

1. Trying every possible start (O(N²) time)
2. Forgetting to reset running fuel when negative
3. Returning start without checking total fuel
4. Assuming multiple valid starting points exist
5. Misunderstanding circular wrapping logic