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. Given the following Python code for assigning cookies to children, what is the final returned value when g = [1, 2, 3] and s = [1, 1]?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace first iteration

   g and s sorted: g=[1,2,3], s=[1,1]. i=0, j=0, count=0. s[0]=1 ≥ g[0]=1 -> count=1, i=1, j=1.

2. Step 2: Trace second iteration

   i=1, j=1, count=1. s[1]=1 < g[1]=2 -> j=2. Loop ends as j=2 equals len(s).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Only one cookie satisfies a child's greed [OK]

Hint: Trace pointer increments carefully [OK]

Common Mistakes:

• Counting cookies not sufficient for greed
• Off-by-one in loop conditions
• Ignoring pointer increments

2. Given the following code and input arrays, what is the final output printed?

def minDominoRotations(A, B):
    def check(x):
        rotations_a = rotations_b = 0
        for i in range(len(A)):
            if A[i] != x and B[i] != x:
                return -1
            elif A[i] != x:
                rotations_a += 1
            elif B[i] != x:
                rotations_b += 1
        return min(rotations_a, rotations_b)

    rotations = check(A[0])
    if rotations != -1:
        return rotations
    else:
        return check(B[0])

A = [3,5,1,2]
B = [3,6,3,3]
print(minDominoRotations(A, B))

easy

A. -1

B. 2

C. 1

D. 3

Solution

1. Step 1: Check candidate x = A[0] = 3

   i=0: A[0]=3 matches x=3, no rotation.
   i=1: A[1]=5 != 3, B[1]=6 != 3 -> return -1 immediately.

2. Step 2: Check candidate x = B[0] = 3

   i=0: A[0]=3 matches x=3, no rotation.
   i=1: A[1]=5 != 3, B[1]=6 != 3 -> return -1 immediately.
   Both candidates fail, so output is -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Both candidates fail at i=1, so no solution [OK]

Hint: Check both candidates carefully for early failure [OK]

Common Mistakes:

• Assuming first candidate always works
• Miscounting rotations when both sides match

3. You have 2n people and need to send exactly n to city A and n to city B. Each person has a different cost for each city. Which approach guarantees the minimum total cost for sending exactly half to each city?

easy

A. Dynamic programming that tries all subsets of people for city A and city B

B. Greedy algorithm sorting people by the difference in their costs between the two cities and assigning the first half to city A and the rest to city B

C. Greedy algorithm sorting people by their absolute cost to city A and assigning the cheapest to city A until full

D. Brute force recursion without memoization to try all assignments

Solution

1. Step 1: Understand problem constraints

   We must send exactly n people to city A and n to city B, minimizing total cost.

2. Step 2: Why sorting by cost difference works

   Sorting by cost difference (cost to A minus cost to B) prioritizes sending people who are cheaper to city A first, and those cheaper to city B later, ensuring minimal total cost.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting by difference balances assignments optimally [OK]

Hint: Sort by cost difference to assign optimally [OK]

Common Mistakes:

• Sorting by absolute cost to one city ignores balance constraint
• Brute force without memoization is too slow
• DP over subsets is correct but inefficient

4. Identify the bug in the following code snippet for the Maximum Units on a Truck problem:

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1])  # Sort ascending instead of descending
    totalUnits = 0
    for boxes, units in boxTypes:
        if truckSize == 0:
            break
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
    return totalUnits

medium

A. Line 2: Sorting boxTypes in ascending order instead of descending

B. Line 5: Missing check for truckSize == 0

C. Line 7: Incorrect calculation of take using min(boxes, truckSize)

D. Line 8: Incorrect update of totalUnits by multiplying take and units

Solution

1. Step 1: Examine sorting order

   Sorting ascending by units per box causes picking boxes with lowest units first, leading to suboptimal total units.

2. Step 2: Verify other lines

   Check for early stopping (line 5) is correct; min calculation and totalUnits update are correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order is critical for greedy correctness [OK]

Hint: Sort descending by units per box to maximize units [OK]

Common Mistakes:

• Sorting ascending instead of descending
• Forgetting to break when truckSize=0
• Off-by-one in min calculation

5. What is the time complexity of the optimal min-heap based algorithm for finding the minimum number of platforms required for n trains?

medium

A. O(n²) due to nested loops checking all train pairs

B. O(n) because each train is processed once

C. O(n log n) due to sorting and heap operations for each train

D. O(n log k) where k is the maximum number of platforms needed

Solution

1. Step 1: Identify sorting cost

   Sorting n trains by arrival time costs O(n log n).

2. Step 2: Analyze heap operations

   Each train causes at most one push and one pop on the heap, each O(log n), so total O(n log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting + heap operations dominate complexity [OK]

Hint: Sorting + heap push/pop per train -> O(n log n) [OK]

Common Mistakes:

• Assuming O(n) ignoring sorting and heap costs
• Confusing heap size k with n for complexity
• Mistaking nested loops for optimal approach complexity