Gas Station - Practice Coding Problems

Gas Station - Problem

Array Greedy Medium

There are n gas stations along a circular route, where the amount of gas at the i^th station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i^th station to its next (i + 1)^th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

If there exists a solution, it is guaranteed to be unique.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Starting from station 3: gas=4, cost=1, remaining=3. Continue to station 4: gas=5, cost=2, total=6. Then stations 0,1,2 can be completed with this surplus.

Example 2 — Impossible Case

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

› Output: -1

💡 Note: Total gas = 9, total cost = 10. Since total cost exceeds total gas, it's impossible to complete the circuit.

Example 3 — Start from Beginning

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

› Output: 4

💡 Note: Starting from station 4 works: 4-1=3, then 5-4=4, total=7, enough to complete the rest of the circuit.

Constraints

1 ≤ gas.length == cost.length ≤ 10⁴
0 ≤ gas[i], cost[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Circular route with gas amounts and travel costs

Process

Find starting point that allows complete circuit

Output

Index of valid starting station or -1

Key Takeaway

🎯 Key Insight: Use greedy approach - when tank goes negative, reset start to next station

Asked in

a Amazon 42 G Google 38 f Facebook 25 M Microsoft 20

The key insight is that if total gas ≥ total cost, there's exactly one valid starting point. Use a greedy approach: when the gas tank goes negative, reset the starting point to the next station. Best approach is greedy one-pass. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy One-Pass Solution	O(n)	O(1)	Find the starting point in one pass using greedy strategy
Try Every Starting Point	O(n²)	O(1)	Test each gas station as a potential starting point

Greedy One-Pass Solution — Algorithm Steps

Check if total gas ≥ total cost
Track current gas tank level
When tank goes negative, reset start to current position

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Feasibility

Verify total gas ≥ total cost

Track Gas Level

Simulate journey, reset start when gas goes negative

Find Answer

Last reset position is the optimal starting point

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* gas, int gasSize, int* cost, int costSize) {
    int totalGas = 0, totalCost = 0;
    
    for (int i = 0; i < gasSize; i++) {
        totalGas += gas[i];
        totalCost += cost[i];
    }
    
    // If total gas < total cost, impossible to complete circuit
    if (totalGas < totalCost) {
        return -1;
    }
    
    int currentGas = 0;
    int start = 0;
    
    for (int i = 0; i < gasSize; i++) {
        currentGas += gas[i] - cost[i];
        
        // If we run out of gas, start from next station
        if (currentGas < 0) {
            currentGas = 0;
            start = i + 1;
        }
    }
    
    return start;
}

int* parseArray(char* str, int* size) {
    int* arr = (int*)malloc(1000 * sizeof(int));
    *size = 0;
    
    char* token = strtok(str + 1, ",]");
    while (token != NULL) {
        arr[*size] = atoi(token);
        (*size)++;
        token = strtok(NULL, ",]");
    }
    
    return arr;
}

int main() {
    char gasStr[10000], costStr[10000];
    fgets(gasStr, sizeof(gasStr), stdin);
    fgets(costStr, sizeof(costStr), stdin);
    
    gasStr[strcspn(gasStr, "\n")] = 0;
    costStr[strcspn(costStr, "\n")] = 0;
    
    int gasSize, costSize;
    int* gas = parseArray(gasStr, &gasSize);
    int* cost = parseArray(costStr, &costSize);
    
    int result = solution(gas, cost, gasSize, cost, costSize);
    printf("%d\n", result);
    
    free(gas);
    free(cost);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array to check feasibility and find starting point

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables to track totals and current state

✓ Linear Space

311.5K Views

High Frequency

~25 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy One-Pass Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler