Gas Station

TIP103 Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Arrays, Greedy Algorithms, Prefix Sums

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What does it mean to complete the circuit?

  • A: Starting at some station with an empty tank, we pick up gas[i] fuel at each station i and spend cost[i] fuel driving to station i + 1, wrapping around the circle. The tank must never drop below zero before we return to the starting station.

• Q: Can there be more than one valid starting station?

  • A: No. The problem guarantees that if a solution exists, it is unique, so we return that single index.

• Q: What should we return if no starting station works?

  • A: Return -1.

HAPPY CASE
Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Explanation: Start at station 3 with 4 units of gas. Travel to station 4 (tank = 4 - 1 + 5 = 8), to station 0 (tank = 8 - 2 + 1 = 7), to station 1 (tank = 7 - 3 + 2 = 6), to station 2 (tank = 6 - 4 + 3 = 5), and back to station 3 (tank = 5 - 5 = 0). The tank never goes negative, so 3 is a valid start.

EDGE CASE
Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1
Explanation: Total gas is 9 but total cost is 10, so no starting station can complete the circuit.

Input: gas = [5], cost = [4]
Output: 0
Explanation: A single station with enough fuel to loop back to itself is trivially a valid start.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Circular Array / Optimization Problems, we can consider the following approaches:

• Greedy: Track the running fuel surplus and discard any starting candidate the moment the tank goes negative — no station between the failed start and the failure point can work either.
• Prefix Sums: Thinking of gas[i] - cost[i] as a running sum makes the greedy insight visible: we want the start whose running sum never dips below zero.
• Brute Force (for contrast): Simulate the full circle from every station, which works but costs O(N^2).

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Work with the net gain gas[i] - cost[i] at each station. If the sum of all net gains is negative, the circuit is impossible, so return -1. Otherwise, sweep the circle once while tracking the surplus since the current candidate start. Whenever the surplus goes negative at station i, every station from the candidate through i is ruled out (each would enter this stretch with even less fuel), so the candidate jumps to i + 1. The candidate remaining at the end is the unique answer.

1) Initialize total_surplus = 0, current_surplus = 0, start = 0.
2) For each station i:
   a) Add gas[i] - cost[i] to both total_surplus and current_surplus.
   b) If current_surplus < 0, the candidate start fails here:
      - Set start = i + 1.
      - Reset current_surplus = 0.
3) If total_surplus < 0, return -1 (not enough gas overall).
4) Otherwise, return start.

⚠️ Common Mistakes

• Simulating the trip from every starting station, which is correct but O(N^2) and too slow for large inputs.
• Forgetting the global check: a start that survives the sweep is only valid if total_surplus >= 0.
• Resetting the candidate to i instead of i + 1 after the tank goes negative at station i.
• Assuming the tank can borrow fuel — it must never drop below zero at any point along the way.

4: I-mplement

Implement the code to solve the algorithm.

def can_complete_circuit(gas, cost):
    total_surplus = 0   # Net fuel across the entire circle
    current_surplus = 0 # Net fuel since the current candidate start
    start = 0           # Candidate starting station

    for i in range(len(gas)):
        gain = gas[i] - cost[i]
        total_surplus += gain
        current_surplus += gain

        # If the tank dips below zero, no station from `start`
        # through `i` can be the answer. Restart at i + 1.
        if current_surplus < 0:
            start = i + 1
            current_surplus = 0

    # A full circuit is possible only if total gas covers total cost
    return start if total_surplus >= 0 else -1

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

  • i = 0: gain = -2, current_surplus = -2 < 0, so start = 1, reset to 0.
  • i = 1: gain = -2, current_surplus = -2 < 0, so start = 2, reset to 0.
  • i = 2: gain = -2, current_surplus = -2 < 0, so start = 3, reset to 0.
  • i = 3: gain = +3, current_surplus = 3.
  • i = 4: gain = +3, current_surplus = 6.
  • total_surplus = 0 >= 0, so we return start.
  • Output: 3

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

  • i = 0: gain = -1, current_surplus = -1 < 0, so start = 1, reset to 0.
  • i = 1: gain = -1, current_surplus = -1 < 0, so start = 2, reset to 0.
  • i = 2: gain = +1, current_surplus = 1.
  • total_surplus = -1 < 0, so no start works.
  • Output: -1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of gas stations.

• Time Complexity: O(N) because we make a single pass over the stations, doing constant work at each one.
• Space Complexity: O(1) because we only keep three scalar variables regardless of input size.