Gas Station (Circular)

🎯

Gas Station (Circular)

mediumGREEDYAmazonFacebookBloomberg

Imagine you have a circular route with gas stations, each providing some fuel, and you want to find a starting station to complete the full circle without running out of gas.

💡 This problem is a classic greedy challenge where beginners often struggle to understand why a simple total fuel check suffices and how to efficiently find the starting station without brute forcing all possibilities.

📋

Problem Statement

Given two integer arrays gas and cost, both of length n, representing n gas stations arranged in a circle: gas[i] is the amount of gas at station i, and cost[i] is the amount of gas required to travel from station i to station (i+1) mod n. Return the starting gas station's index if you can travel around the circuit once in the clockwise direction without running out of gas; otherwise, return -1.

1 ≤ n ≤ 10^50 ≤ gas[i], cost[i] ≤ 10^4

💡

Example

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

Output3

Starting at station 3, you can complete the circuit: gas[3]=4, cost[3]=1, net +3; then station 4 net +3; stations 0,1,2 net negative but total gas is enough to cover cost.

• All gas[i] equal to cost[i] → return any valid index (usually 0)
• Total gas less than total cost → return -1
• Single station with gas[i] >= cost[i] → return 0
• Stations with zero gas but enough total gas → valid start exists

⚠️

Common Mistakes

Not checking total gas vs total cost before starting

Returns incorrect start index or infinite loop

✅ Add a check if sum(gas) < sum(cost) return -1

Resetting start but forgetting to reset tank

Tank accumulates negative values causing wrong results

✅ Reset tank to 0 when resetting start

Using modulo incorrectly causing index errors

Runtime errors or wrong indexing in circular traversal

✅ Use (start + i) % n for circular indexing

Trying to find multiple valid starts instead of one

Wastes time or returns wrong answer

✅ Return the first valid start found

Confusing gas and cost arrays or mixing their roles

Incorrect calculations leading to wrong output

✅ Carefully subtract cost from gas at each station

🧠

Brute Force (Check Each Station as Start)

💡 This approach exists to build intuition by trying every possible start and simulating the trip, which helps understand the problem's constraints and why a better approach is needed.

Intuition

Try starting from each gas station and simulate traveling around the circle to see if you can complete the circuit without running out of gas.

Algorithm

1. For each station i from 0 to n-1:
2. Initialize tank = 0 and count stations traveled = 0
3. While count < n, add gas at current station and subtract cost to next station
4. If tank becomes negative, break and try next station
5. If completed n stations, return i as start

💡 The nested loops and simulation make it hard to see efficiency, but it directly models the problem.

</>

Code

def canCompleteCircuit(gas, cost):
    n = len(gas)
    for start in range(n):
        tank = 0
        completed = True
        for i in range(n):
            idx = (start + i) % n
            tank += gas[idx] - cost[idx]
            if tank < 0:
                completed = False
                break
        if completed:
            return start
    return -1

# Driver code
if __name__ == '__main__':
    gas = [1,2,3,4,5]
    cost = [3,4,5,1,2]
    print(canCompleteCircuit(gas, cost))  # Output: 3

Line Notes

for start in range(n):Try each station as a potential start

tank = 0Reset tank for each start attempt

idx = (start + i) % nCircular indexing to simulate the route

if tank < 0:If tank negative, cannot complete from this start

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int start = 0; start < n; start++) {
            int tank = 0;
            boolean completed = true;
            for (int i = 0; i < n; i++) {
                int idx = (start + i) % n;
                tank += gas[idx] - cost[idx];
                if (tank < 0) {
                    completed = false;
                    break;
                }
            }
            if (completed) return start;
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        System.out.println(sol.canCompleteCircuit(gas, cost)); // Output: 3
    }
}

Line Notes

for (int start = 0; start < n; start++) {Try each station as start

int tank = 0;Reset tank for each start

int idx = (start + i) % n;Circular indexing for stations

if (tank < 0) {Break early if tank negative

#include <iostream>
#include <vector>
using namespace std;

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int n = gas.size();
    for (int start = 0; start < n; start++) {
        int tank = 0;
        bool completed = true;
        for (int i = 0; i < n; i++) {
            int idx = (start + i) % n;
            tank += gas[idx] - cost[idx];
            if (tank < 0) {
                completed = false;
                break;
            }
        }
        if (completed) return start;
    }
    return -1;
}

int main() {
    vector<int> gas = {1,2,3,4,5};
    vector<int> cost = {3,4,5,1,2};
    cout << canCompleteCircuit(gas, cost) << endl; // Output: 3
    return 0;
}

Line Notes

for (int start = 0; start < n; start++) {Try each station as start

int tank = 0;Reset tank for each attempt

int idx = (start + i) % n;Circular indexing for stations

if (tank < 0) {Break early if tank negative

function canCompleteCircuit(gas, cost) {
    const n = gas.length;
    for (let start = 0; start < n; start++) {
        let tank = 0;
        let completed = true;
        for (let i = 0; i < n; i++) {
            const idx = (start + i) % n;
            tank += gas[idx] - cost[idx];
            if (tank < 0) {
                completed = false;
                break;
            }
        }
        if (completed) return start;
    }
    return -1;
}

// Test
console.log(canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])); // Output: 3

Line Notes

for (let start = 0; start < n; start++) {Try each station as start

let tank = 0;Reset tank for each start attempt

const idx = (start + i) % n;Circular indexing for stations

if (tank < 0) {Break early if tank negative

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each station, we simulate traveling all n stations, resulting in n*n operations.

💡 For n=1000, this means about 1,000,000 operations, which is too slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and correctness.

🧠

Greedy with Total Gas Check and Reset Start

💡 This approach improves efficiency by using a greedy strategy that resets the start station when the tank goes negative, leveraging the insight that if you can't reach station j from i, no station between i and j can be a valid start.

Intuition

If total gas is less than total cost, no solution exists. Otherwise, track the tank while iterating; if tank drops below zero, reset start to next station and reset tank.

Algorithm

1. Check if total gas is at least total cost; if not, return -1
2. Initialize start = 0, tank = 0
3. Iterate over stations, update tank += gas[i] - cost[i]
4. If tank < 0, reset start to i+1 and tank to 0
5. Return start after iteration

💡 The key insight is that a negative tank means the current start is invalid, so we move start forward.

</>

Code

def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = 0
    tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start

# Driver code
if __name__ == '__main__':
    gas = [1,2,3,4,5]
    cost = [3,4,5,1,2]
    print(canCompleteCircuit(gas, cost))  # Output: 3

Line Notes

if sum(gas) < sum(cost):Check overall feasibility before proceeding

start = 0Initialize start index

tank += gas[i] - cost[i]Update tank with net gas at station i

if tank < 0:Reset start and tank if current start fails

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0;
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
        }
        if (totalGas < totalCost) return -1;
        int start = 0, tank = 0;
        for (int i = 0; i < gas.length; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return start;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        System.out.println(sol.canCompleteCircuit(gas, cost)); // Output: 3
    }
}

Line Notes

if (totalGas < totalCost) return -1;Quick feasibility check

int start = 0, tank = 0;Initialize start and tank

tank += gas[i] - cost[i];Update tank with net gas

if (tank < 0) {Reset start and tank when tank negative

#include <iostream>
#include <vector>
using namespace std;

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int totalGas = 0, totalCost = 0;
    for (int i = 0; i < gas.size(); i++) {
        totalGas += gas[i];
        totalCost += cost[i];
    }
    if (totalGas < totalCost) return -1;
    int start = 0, tank = 0;
    for (int i = 0; i < gas.size(); i++) {
        tank += gas[i] - cost[i];
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return start;
}

int main() {
    vector<int> gas = {1,2,3,4,5};
    vector<int> cost = {3,4,5,1,2};
    cout << canCompleteCircuit(gas, cost) << endl; // Output: 3
    return 0;
}

Line Notes

if (totalGas < totalCost) return -1;Check if trip is possible overall

int start = 0, tank = 0;Initialize start and tank

tank += gas[i] - cost[i];Update tank with net gas at station i

if (tank < 0) {Reset start and tank if current start fails

function canCompleteCircuit(gas, cost) {
    const totalGas = gas.reduce((a,b) => a+b, 0);
    const totalCost = cost.reduce((a,b) => a+b, 0);
    if (totalGas < totalCost) return -1;
    let start = 0, tank = 0;
    for (let i = 0; i < gas.length; i++) {
        tank += gas[i] - cost[i];
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return start;
}

// Test
console.log(canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])); // Output: 3

Line Notes

if (totalGas < totalCost) return -1;Check overall feasibility

let start = 0, tank = 0;Initialize start and tank

tank += gas[i] - cost[i];Update tank with net gas

if (tank < 0) {Reset start and tank when tank negative

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the arrays with constant extra space.

💡 For n=100000, this means 100000 operations, which is efficient and scalable.

Interview Verdict: Accepted

This is the optimal and accepted approach for interviews.

🧠

Greedy with Prefix Sum and Two Pointers (Alternative View)

💡 This approach uses prefix sums and two pointers to find the start station, providing an alternative perspective that can help understand the problem's circular nature.

Intuition

Calculate net gas at each station, then use two pointers to find a subarray of length n with non-negative sum, which corresponds to a valid start.

Algorithm

1. Compute net array = gas[i] - cost[i]
2. Create prefix sums of net array twice (to simulate circular)
3. Use two pointers to find a window of length n with non-negative sum
4. Return start index if found, else -1

💡 This approach is more complex but reinforces understanding of circular arrays and prefix sums.

</>

Code

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    if sum(net) < 0:
        return -1
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    start = 0
    end = n
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

# Driver code
if __name__ == '__main__':
    gas = [1,2,3,4,5]
    cost = [3,4,5,1,2]
    print(canCompleteCircuit(gas, cost))  # Output: 3

Line Notes

net = [gas[i] - cost[i] for i in range(n)]Calculate net gas at each station

if sum(net) < 0:Check overall feasibility

prefix[i+1] = prefix[i] + net[i % n]Build prefix sums for circular array

if prefix[i+n] - prefix[i] >= 0:Check if window sum is non-negative

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int[] net = new int[n];
        int total = 0;
        for (int i = 0; i < n; i++) {
            net[i] = gas[i] - cost[i];
            total += net[i];
        }
        if (total < 0) return -1;
        int[] prefix = new int[2 * n + 1];
        for (int i = 0; i < 2 * n; i++) {
            prefix[i+1] = prefix[i] + net[i % n];
        }
        for (int i = 0; i < n; i++) {
            if (prefix[i+n] - prefix[i] >= 0) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        System.out.println(sol.canCompleteCircuit(gas, cost)); // Output: 3
    }
}

Line Notes

net[i] = gas[i] - cost[i];Calculate net gas at each station

if (total < 0) return -1;Check overall feasibility

prefix[i+1] = prefix[i] + net[i % n];Build prefix sums for circular array

if (prefix[i+n] - prefix[i] >= 0) return i;Check if window sum is non-negative

#include <iostream>
#include <vector>
using namespace std;

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int n = gas.size();
    vector<int> net(n);
    int total = 0;
    for (int i = 0; i < n; i++) {
        net[i] = gas[i] - cost[i];
        total += net[i];
    }
    if (total < 0) return -1;
    vector<int> prefix(2 * n + 1, 0);
    for (int i = 0; i < 2 * n; i++) {
        prefix[i+1] = prefix[i] + net[i % n];
    }
    for (int i = 0; i < n; i++) {
        if (prefix[i+n] - prefix[i] >= 0) return i;
    }
    return -1;
}

int main() {
    vector<int> gas = {1,2,3,4,5};
    vector<int> cost = {3,4,5,1,2};
    cout << canCompleteCircuit(gas, cost) << endl; // Output: 3
    return 0;
}

Line Notes

net[i] = gas[i] - cost[i];Calculate net gas at each station

if (total < 0) return -1;Check overall feasibility

prefix[i+1] = prefix[i] + net[i % n];Build prefix sums for circular array

if (prefix[i+n] - prefix[i] >= 0) return i;Check if window sum is non-negative

function canCompleteCircuit(gas, cost) {
    const n = gas.length;
    const net = gas.map((g, i) => g - cost[i]);
    const total = net.reduce((a,b) => a+b, 0);
    if (total < 0) return -1;
    const prefix = new Array(2 * n + 1).fill(0);
    for (let i = 0; i < 2 * n; i++) {
        prefix[i+1] = prefix[i] + net[i % n];
    }
    for (let i = 0; i < n; i++) {
        if (prefix[i+n] - prefix[i] >= 0) return i;
    }
    return -1;
}

// Test
console.log(canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])); // Output: 3

Line Notes

const net = gas.map((g, i) => g - cost[i]);Calculate net gas at each station

if (total < 0) return -1;Check overall feasibility

prefix[i+1] = prefix[i] + net[i % n];Build prefix sums for circular array

if (prefix[i+n] - prefix[i] >= 0) return i;Check if window sum is non-negative

⏱

Complexity

TimeO(n)

SpaceO(n)

Prefix sums and iteration over 2n elements, linear time and space.

💡 This approach uses extra space but still runs efficiently for large inputs.

Interview Verdict: Accepted

This approach is correct and accepted but less common than the reset start greedy.

📊

All Approaches - One-Glance Tradeoffs

💡 The greedy with reset start approach is the best to code in interviews due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Greedy with Reset Start	O(n)	O(1)	No	N/A	Code this approach
3. Prefix Sum and Two Pointers	O(n)	O(n)	No	N/A	Mention as alternative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare for common follow-ups.

How to Present

Clarify problem constraints and circular natureExplain brute force approach to show understandingIntroduce greedy approach with total gas check and reset startCode the optimal greedy solutionTest with edge cases and explain complexity

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of greedy strategy, ability to optimize brute force, handling edge cases, and coding correctness.

Common Follow-ups

• What if gas and cost arrays are very large? → Use O(n) greedy approach
• Can you explain why resetting start works? → Because no station between old start and failure point can be valid

💡 These follow-ups test deeper understanding of the greedy insight and scalability.

🔍

Pattern Recognition

When to Use

1) Circular array or route involved, 2) Need to find a start point to complete a cycle, 3) Gas or resource constraints, 4) Greedy or prefix sums applicable

Signature Phrases

complete the circuitstarting gas stationcircular route

NOT This Pattern When

Problems involving linear traversal without circular constraints or without resource balancing

Similar Problems

Candy - distributing resources with constraintsJump Game II - minimum jumps to reach endMinimum Number of Refueling Stops - optimizing stops on a route

Practice

1. Consider the following code snippet implementing the peak-valley approach to maximize stock profit. What is the final returned profit when the input prices are [1, 2, 3]?

def maxProfit(prices):
    i = 0
    profit = 0
    n = len(prices)
    while i < n - 1:
        while i < n - 1 and prices[i] >= prices[i + 1]:
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i] <= prices[i + 1]:
            i += 1
        peak = prices[i]
        profit += peak - valley
    return profit

easy

A. 2

B. 0

C. 3

D. 1

Solution

1. Step 1: Trace first while loop to find valley

   i=0, prices[0]=1, prices[1]=2, 1 < 2 so inner loop skips, valley=1

2. Step 2: Trace second while loop to find peak

   i increments while prices[i] <= prices[i+1]: i=0 to 1 (2 <= 3), i=1 to 2 (3 no next), peak=3

3. Step 3: Calculate profit and return

   profit += 3 - 1 = 2, loop ends, return 2

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Profit matches sum of positive differences (2) [OK]

Hint: Sum of (3-1) = 2 profit [OK]

Common Mistakes:

• Off-by-one error missing last peak
• Confusing valley and peak assignments
• Returning zero if no decreasing sequence found

2. Consider the following Python code that computes the minimum cost to connect sticks using a min-heap. What is the value of total_cost returned when the input is [1, 8, 3, 5]?

easy

A. 30

B. 36

C. 33

D. 29

Solution

1. Step 1: Trace initial heap and first merge

   Heapify sticks: [1,3,5,8]. Pop 1 and 3 -> cost=4, total_cost=4. Push 4 back -> heap: [4,5,8]

2. Step 2: Trace second and third merges

   Pop 4 and 5 -> cost=9, total_cost=13. Push 9 -> heap: [8,9]. Pop 8 and 9 -> cost=17, total_cost=30. Push 17 -> heap: [17]. Loop ends.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of merges: 4 + 9 + 17 = 30 [OK]

Hint: Sum merges stepwise using min-heap pops [OK]

Common Mistakes:

• Adding costs incorrectly or missing last merge
• Confusing heap order or popping wrong elements
• Off-by-one in loop iterations

3. Consider the following Python function that calculates the minimum number of platforms needed. Given the input arrivals = [900, 940, 950] and departures = [910, 1200, 1120], what is the value of max_platforms after processing the second train (index 1)?

easy

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Sort trains by arrival time

   Sorted trains: [(900, 910), (940, 1200), (950, 1120)]

2. Step 2: Process trains up to index 1

   After first train: heap=[910], max_platforms=1 Second train arrival=940, heap top=910 ≤ 940, pop 910 Push 1200, heap=[1200], max_platforms=max(1,1)=1 Since question asks after second train, max_platforms=1

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap size after second train is 1, max_platforms updated to 1 [OK]

Hint: Heap pops departures ≤ arrival before push [OK]

Common Mistakes:

• Not popping from heap before push
• Confusing max_platforms update timing
• Off-by-one in iteration

4. Given the following code and input, what is the final returned total cost?

def twoCitySchedCost(costs):
    costs.sort(key=lambda x: x[0] - x[1])
    n = len(costs) // 2
    total = 0
    for i, cost in enumerate(costs):
        if i < n:
            total += cost[0]
        else:
            total += cost[1]
    return total

costs = [[10,20],[30,200],[400,50],[30,20]]
print(twoCitySchedCost(costs))

easy

A. 110

B. 150

C. 120

D. 140

Solution

1. Step 1: Sort costs by difference cost[0] - cost[1]

   Differences: [10-20=-10, 30-200=-170, 400-50=350, 30-20=10]. Sorted: [[30,200], [10,20], [30,20], [400,50]]

2. Step 2: Assign first half to city A, rest to city B and sum costs

   First two: city A costs = 30 + 10 = 40; last two: city B costs = 20 + 50 = 70; total = 40 + 70 = 110

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum matches manual calculation [OK]

Hint: Sort by difference, assign first half to city A [OK]

Common Mistakes:

• Misordering after sorting by difference
• Off-by-one in loop boundary
• Adding wrong city cost for last half

5. What is the time complexity of the optimal greedy algorithm for the wiggle subsequence problem, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because it scans the list once, updating counters based on difference signs

B. O(2^n) because it explores all subsequences recursively

C. O(n log n) due to sorting or binary search steps involved

D. O(n^2) because it compares each element with all previous elements

Solution

1. Step 1: Analyze algorithm operations

   The greedy algorithm iterates through the list once, computing differences and updating counters in O(1) time per element.

2. Step 2: Address common misconceptions

   Some candidates confuse it with brute force or DP approaches, thinking it compares pairs or explores subsequences exponentially, leading to O(n^2) or O(2^n) assumptions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant work per element -> O(n) [OK]

Hint: Single pass with constant updates -> O(n)

Common Mistakes:

• Confusing with brute force exponential time
• Assuming nested loops for comparisons
• Thinking sorting is involved