30. Gas Station

The problem can be found at the following link: Question Link

Problem Description

There are some gas stations along a circular route. You are given two integer arrays gas[] (the amount of gas at each station) and cost[] (the cost to travel to the next station).

You have a car with an unlimited gas tank and you start the journey with an empty tank from one of the gas stations.

Return the index of the starting gas station if it's possible to travel around the circuit without running out of gas at any station in a clockwise direction. If no such starting station exists, return -1. Note: If a solution exists, it is guaranteed to be unique.

Note: Sorry for uploading late, my exam is going on.

Examples

Example 1:

Input:

gas[] = [4, 5, 7, 4]
cost[] = [6, 6, 3, 5]

Output:

2

Explanation:

• Start at index 2 (gas = 7).

• Travel to index 3: 7 - 3 + 4 = 8 (gas left).

• Travel to index 0: 8 - 5 + 4 = 7 (gas left).

• Travel to index 1: 7 - 6 + 5 = 6 (gas left).

• Return to index 2: 6 - 6 = 0 (gas left). Hence, starting from index 2 allows a complete circuit.

Example 2:

Input:

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

Output:

3

Explanation:

• Start at index 3 (gas = 4).

• Travel to index 4: 4 - 1 + 5 = 8 (gas left).

• Travel to index 0: 8 - 2 + 1 = 7 (gas left).

• Travel to index 1: 7 - 3 + 2 = 6 (gas left).

• Travel to index 2: 6 - 4 + 3 = 5 (gas left).

• Return to index 3: 5 - 5 = 0 (gas left). Hence, starting from index 3 allows a complete circuit.

Example 3:

Input:

gas[] = [3, 9]
cost[] = [7, 6]

Output:

-1

Explanation: There is no gas station to start such that you can complete the circuit.

Constraints:

• $(1 \leq \text{gas.size()}, \text{cost.size()} \leq 10^6)$

• $(1 \leq \text{gas}[i], \text{cost}[i] \leq 10^3)$

My Approach

Greedy (Optimized)

Algorithm Steps:

1. Traverse the gas stations and maintain:

   • total: Total difference between gas and cost.

   • curr: Current gas balance.

   • start: Starting index.

2. For each station:

   • Calculate the difference: diff = gas[i] - cost[i].

   • Add diff to total and curr.

   • If curr < 0, it means that starting from the current start is not possible, so:

     • Update start = i + 1.

     • Reset curr = 0.

3. After traversing all stations:

   • If total >= 0, return start.

   • Otherwise, return -1.

Time and Auxiliary Space Complexity

• Expected Time Complexity: (O(N)), as we traverse the gas stations once.

• Expected Auxiliary Space Complexity: (O(1)), since we use only a few variables for calculation.

Code (C++)

class Solution {
  public:
    int startStation(vector<int>& gas, vector<int>& cost) {
        int total = 0, curr = 0, start = 0;
        for (int i = 0; i < gas.size(); i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            curr += diff;
            if (curr < 0) start = i + 1, curr = 0;
        }
        return total >= 0 ? start : -1;
    }
};

⚡ Alternative Approaches

📊 2️⃣ Two-Pass Approach

Algorithm Steps:

1. Calculate the total gas balance.

2. If the total gas is negative, it's impossible to complete the circuit.

3. If positive, find the optimal start point.

class Solution {
  public:
    int startStation(vector<int>& gas, vector<int>& cost) {
        int total = 0, curr = 0, start = 0;
        for (int i = 0; i < gas.size(); i++) {
            total += gas[i] - cost[i];
            curr += gas[i] - cost[i];
            if (curr < 0) {
                start = i + 1;
                curr = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
};

📝 Complexity Analysis:

• ✅ Time Complexity: O(N) - We traverse the gas stations twice in the worst case.

• ✅ Space Complexity: O(1) - Only a few variables are used.

✅ Why This Approach?

This method is intuitive, as it first ensures the total gas is non-negative and then finds the optimal start point.

🔁 3️⃣ Prefix Sum Approach

Algorithm Steps:

1. Calculate the total gas balance.

2. Track the cumulative gas difference while iterating.

3. If the cumulative gas drops below 0, update the start to the next station.

class Solution {
  public:
    int startStation(vector<int>& gas, vector<int>& cost) {
        int total = 0, sum = 0, start = 0;
        for (int i = 0; i < gas.size(); i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            sum += diff;
            if (sum < 0) {
                start = i + 1;
                sum = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
};

📝 Complexity Analysis:

• ✅ Time Complexity: O(N)

• ✅ Space Complexity: O(1)

✅ Why This Approach?

Uses cumulative gas difference to determine a viable start point while maintaining efficiency.

🔄 4️⃣ Efficient Circular Check

Algorithm Steps:

1. Traverse the array in a circular manner using modular arithmetic.

2. If the current gas balance becomes negative, reset the start station to the next one.

3. If the total gas is positive, return the start station, otherwise return -1.

class Solution {
  public:
    int startStation(vector<int>& gas, vector<int>& cost) {
        int total = 0, curr = 0, start = 0;
        int n = gas.size();
        for (int i = 0; i < 2 * n; i++) {
            int index = i % n;
            int diff = gas[index] - cost[index];
            total += diff;
            curr += diff;
            if (curr < 0) {
                start = index + 1;
                curr = 0;
                if (start >= n) break;
            }
        }
        return total >= 0 ? start : -1;
    }
};

📝 Complexity Analysis:

• ✅ Time Complexity: O(N)

• ✅ Space Complexity: O(1)

✅ Why This Approach?

Efficiently handles circular routes using modular arithmetic while keeping the logic simple.

🆚 Comparison of Approaches

Approach	⏱️ Time Complexity	🗂️ Space Complexity	✅ Pros	⚠️ Cons
Greedy (Optimized)	🟢 O(N)	🟢 O(1)	Best performance, minimal space	Harder to derive intuitively
Two-Pass Approach	🟢 O(N)	🟢 O(1)	Simple to understand, efficient	Requires two passes in some scenarios
Prefix Sum Approach	🟢 O(N)	🟢 O(1)	Simple logic with cumulative sum	Not significantly different from greedy
Efficient Circular Check	🟢 O(N)	🟢 O(1)	Handles circular cases effectively	Slightly more complex logic

✅ Best Choice?

• Use the Greedy (Optimized) for maximum efficiency.

• The Two-Pass or Prefix Sum are suitable for simpler implementation.

• The Efficient Circular Check is ideal for circular track scenarios.

Code (Java)

class Solution {
    public int startStation(int[] gas, int[] cost) {
        int total = 0, curr = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            curr += diff;
            if (curr < 0) { start = i + 1; curr = 0; }
        }
        return total >= 0 ? start : -1;
    }
}

Code (Python)

class Solution:
    def startStation(self, gas, cost):
        total = curr = start = 0
        for i in range(len(gas)):
            diff = gas[i] - cost[i]
            total += diff
            curr += diff
            if curr < 0: start, curr = i + 1, 0
        return start if total >= 0 else -1

Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count