← Back to Index

📚 Gas Station – Java Cheat Sheet

📌 What Is It?

The Gas Station problem involves finding the starting gas station index from which you can complete a circular route around all gas stations. Each station provides a certain amount of gas, and you need a certain amount of gas to travel to the next station.

🧱 Pattern Template

Greedy Algorithm

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0, startIndex = 0, currentTank = 0;

        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            currentTank += gas[i] - cost[i];

            if (currentTank < 0) {
                startIndex = i + 1; // Reset starting point
                currentTank = 0;   // Reset current tank
            }
        }

        return totalGas >= totalCost ? startIndex : -1; // Check if a solution exists
    }
}

▶️ View Animation

📊 Time Complexity

• Time Complexity: O(N), where N is the number of gas stations. We iterate through the array once.
• Space Complexity: O(1), as we use only a constant amount of extra space.

✅ Use Cases

• Finding the optimal starting point in circular traversal problems.
• Solving problems involving cumulative sums and resets.

📘 Common LeetCode Problems

• 134. Gas Station [Medium] Greedy

🧪 Example

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

Explanation:
- Start at station 3 (0-based index).
- Travel around the circuit and return to station 3 with a non-negative tank.

💡 Pro Tips

• If the total gas is less than the total cost, it's impossible to complete the circuit.
• Reset the starting index whenever the current tank becomes negative.
• Use a greedy approach to minimize unnecessary computations.

🎥 Video Explanation

For a detailed explanation, watch this video: Gas Station Problem Explanation by Shradha Khapra