Gas Station

Last Updated : 6 Sep, 2025

Given two arrays gas[] and cost[], each gas station i provides gas[i] fuel, and it takes cost[i] fuel to travel to the next station. Starting with an empty tank, find the index of the gas station from which you can complete a full circular tour. If it’s not possible, return -1.

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

Examples:

Input: gas[] = [4, 5, 7, 4], cost[] = [6, 6, 3, 5]
Output: 2
Explanation: Start at gas station at index 2 and fill up with 7 units of gas. Your tank = 0 + 7 = 7
Travel to station 3. Available gas = (7 - 3 + 4) = 8.
Travel to station 0. Available gas = (8 - 5 + 4) = 7.
Travel to station 1. Available gas = (7 - 6 + 5) = 6.
Return to station 2. Available gas = (6 - 6) = 0.
Therefore, 2 is the starting index.
Input: gas[] = [3, 9], cost[] = [7, 6]
Output: -1
Explanation: There is no gas station to start with such that you can complete the tour.

Try it on GfG Practice

Table of Content

[Naive Approach] Considering Every Index as Starting Point - O(n^2) Time and O(1) Space
[Expected Approach 1] Greedy Approach - O(n) Time and O(1) Space
[Expected Approach 2] Greedy Approach in One Pass - O(n) Time and O(1) Space

[Naive Approach] Considering Every Index as Starting Point - O(n²) Time and O(1) Space

The simplest approach is to consider each index as a starting point and check if a car can complete the circular tour starting from that index. If we find a valid starting point, we will return it.

C++

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

int startStation(vector<int> &gas, vector<int> &cost) {
    int n = gas.size();
    int startIdx = -1;
    for(int i = 0; i < n; i++) {
        
        // Initially tank is empty
        int currGas = 0;
        bool flag = true;
        for (int j = 0; j < n; j++){
            
            // Circular Index
            int idx = (i + j) % n;
            currGas = currGas + gas[idx] - cost[idx];
            
            // If currGas is less than zero, then it isn't
            // possible to proceed further with this starting point
            if(currGas < 0) {
                flag = false;
                break;  
            }
        }
        
        // If flag is true, then we have found
        // the valid starting point
        if(flag) {
            startIdx = i;
            break;
        }
    }
    return startIdx;
}

int main() {
    vector<int> gas = {4, 5, 7, 4};
    vector<int> cost = {6, 6, 3, 5};
    cout << startStation(gas, cost) << endl;
    return 0;
}

C

#include <stdio.h>

int startStation(int gas[], int cost[], int n) {
    int startIdx = -1;
    for (int i = 0; i < n; i++) {
        
        // Current Available gas
        int currGas = 0;
        int flag = 1;
        for (int j = 0; j < n; j++) {
            
            // Circular Index
            int idx = (i + j) % n;
            currGas = currGas + gas[idx] - cost[idx];
            
            // If Available gas is less than zero, then it isn't
            // possible to proceed further with this starting point
            if (currGas < 0) {
                flag = 0;
                break;
            }
        }
      
        // If flag is true, then we have found
        // the valid starting point
        if (flag) {
            startIdx = i;
            break;
        }
    }
    
    return startIdx;
}

int main() {
    int gas[] = {4, 5, 7, 4};
    int cost[] = {6, 6, 3, 5};
    int n = sizeof(gas) / sizeof(gas[0]);
    printf("%d\n", startStation(gas, cost, n));
    return 0;
}

Java

class GfG {
    static int startStation(int[] gas, int[] cost) {
        int n = gas.length;
        int startIdx = -1;
        for (int i = 0; i < n; i++) {
            
            // Current Available gas
            int currGas = 0;
            boolean flag = true;
            for (int j = 0; j < n; j++) {
                
                // Circular Index
                int idx = (i + j) % n;
                currGas = currGas + gas[idx] - cost[idx];
                
                // If Available gas is less than zero, then it isn't
                // possible to proceed further with this starting point
                if (currGas < 0) {
                    flag = false;
                    break;
                }
            }
            
          	// If flag is true, then we have found
      		// the valid starting point
            if (flag) {
                startIdx = i;
                break;
            }
        }
        
        return startIdx;
    }
    
    public static void main(String[] args) {
        int[] gas = {4,5,7,4};
        int[] cost = {6, 6, 3, 5};
        System.out.println(startStation(gas, cost));
    }
}

Python

def startStation(gas, cost):
    n = len(gas)
    startIdx = -1
    
    for i in range(n):
        
        # Current Available gas
        currGas = 0
        flag = True
        
        for j in range(n):
            
            # Circular Index
            idx = (i + j) % n
            currGas += gas[idx] - cost[idx]
            
            # If Available gas is less than zero, then it isn't
            # possible to proceed further with this starting point
            if currGas < 0:
                flag = False
                break
        
        # If flag is true, then we have found
      	# the valid starting point
        if flag:
            startIdx = i
            break
    
    return startIdx
  	
if __name__ == "__main__":
    gas = [4,5,7,4]
    cost = [6, 6, 3, 5]
    print(startStation(gas, cost))

C#

using System;

class GfG {
    static int startStation(int[] gas, int[] cost) {
        int n = gas.Length;
        int startIdx = -1;
        for (int i = 0; i < n; i++) {
            
            // Current Available gas
            int currGas = 0;
            bool flag = true;
            for (int j = 0; j < n; j++) {
                
                // Circular Index
                int idx = (i + j) % n;
                currGas = currGas + gas[idx] - cost[idx];
                
                // If Available gas is less than zero, then it isn't
                // possible to proceed further with this starting point
                if (currGas < 0) {
                    flag = false;
                    break;
                }
            }
            
            // If flag is true, then we have found
            // the valid starting point
            if (flag) {
                startIdx = i;
                break;
            }
        }
        
        return startIdx;
    }

    static void Main() {
        int[] gas = { 4,5,7,4 };
        int[] cost = { 6, 6, 3, 5 };
        Console.WriteLine(startStation(gas, cost));
    }
}

JavaScript

function startStation(gas, cost) {
    let n = gas.length;
    let startIdx = -1;
    
    for (let i = 0; i < n; i++) {
        
        // Current Available gas
        let currGas = 0;
        let flag = true;
        
        for (let j = 0; j < n; j++) {
            
            // Circular Index
            let idx = (i + j) % n;
            currGas += gas[idx] - cost[idx];
            
            // If Available gas is less than zero, then it isn't
            // possible to proceed further with this starting point
            if (currGas < 0) {
                flag = false;
                break;
            }
        }
        
        // If flag is true, then we have found
      	// the valid starting point
        if (flag) {
            startIdx = i;
            break;
        }
    }
    
    return startIdx;
}

// Driver Code
let gas = [4, 5, 7, 4];
let cost = [6, 6, 3, 5];
console.log(startStation(gas, cost));

Output

[Expected Approach 1] Greedy Approach - O(n) Time and O(1) Space

The idea is maintain the available gas while traversing. If it ever drops below zero at station i, the journey cannot start from the current starting point, so we shift the starting point to i + 1.

How it Works?

At each station i, update available gas as: available gas + gas[i] - cost[i].
If available gas < 0 reset starting point to i + 1 and continue.
After completing the traversal, check if the chosen starting point can cover the circular tour.

Note: If starting from index s fails at station i (available gas < 0), then no station between s and i can be a valid start either because each of them would reach station i with even less gas than starting at s. Therefore, the next possible candidate is i + 1.

C++

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

int startStation(vector<int> &gas, vector<int> &cost) {
    int n = gas.size();
    int startIdx = 0;
    
    // Initially tank is empty
    int currGas = 0;
    
    for(int i = 0; i < n; i++) {
        currGas = currGas + gas[i] - cost[i];
        
        // If currGas becomes less than zero, then
        // It's not possible to proceed with this startIdx
        if(currGas < 0) {
            startIdx = i + 1;
            currGas = 0;
        }
    }
    
    
    // Checking if startIdx can be a valid 
    // starting point for the Circular tour
    currGas = 0;
    for(int i = 0; i < n; i++) {
        
        // Circular Index
        int idx = (i + startIdx) % n;
      	currGas = currGas + gas[idx] - cost[idx];
        if(currGas < 0)
            return -1;
    }
    
    return startIdx;
}

int main() {
    vector<int> gas = {4,5,7,4};
    vector<int> cost = {6, 6, 3, 5};
    cout << startStation(gas, cost) << endl;
    return 0;
}

C

#include <stdio.h>

int startStation(int gas[], int cost[], int n) {
    int startIdx = 0;

    // Initially tank is empty
    int currGas = 0;

    for (int i = 0; i < n; i++) {
        currGas = currGas + gas[i] - cost[i];

        // If currGas becomes less than zero, then
        // It's not possible to proceed with this startIdx
        if (currGas < 0) {
            startIdx = i + 1;
            currGas = 0;
        }
    }

    // Checking if startIdx can be a valid 
    // starting point for the Circular tour.
    currGas = 0;
    for (int i = 0; i < n; i++) {

        // Circular Index
        int idx = (i + startIdx) % n;
        currGas = currGas + gas[idx] - cost[idx];
        if (currGas < 0)
            return -1;
    }

    return startIdx;
}

int main() {
    int gas[] = {4,5,7,4};
    int cost[] = {6, 6, 3, 5};
    int n = sizeof(gas) / sizeof(gas[0]);
    printf("%d\n", startStation(gas, cost, n));
    return 0;
}

Java

class GfG {
    static int startStation(int[] gas, int[] cost) {
        int n = gas.length;
        int startIdx = 0;

        // Initially tank is empty
        int currGas = 0;

        for (int i = 0; i < n; i++) {
            currGas = currGas + gas[i] - cost[i];

            // If currGas becomes less than zero, then
            // It's not possible to proceed with this startIdx
            if (currGas < 0) {
                startIdx = i + 1;
                currGas = 0;
            }
        }

        // Checking if startIdx can be a valid 
    	// starting point for the Circular tour
        currGas = 0;
        for (int i = 0; i < n; i++) {

            // Circular Index
            int idx = (i + startIdx) % n;
            currGas = currGas + gas[idx] - cost[idx];
            if (currGas < 0)
                return -1;
        }

        return startIdx;
    }

    public static void main(String[] args) {
        int[] gas = {4,5,7,4};
        int[] cost = {6, 6, 3, 5};
        System.out.println(startStation(gas, cost));
    }
}

Python

def startStation(gas, cost):
    n = len(gas)
    startIdx = 0

    # Initially tank is empty
    currGas = 0

    for i in range(n):
        currGas = currGas + gas[i] - cost[i]

        # If currGas becomes less than zero, then
        # It's not possible to proceed with this startIdx
        if currGas < 0:
            startIdx = i + 1
            currGas = 0

    # Checking if startIdx can be a valid 
    # starting point for the Circular tour
    currGas = 0
    for i in range(n):

        # Circular Index
        idx = (i + startIdx) % n
        currGas = currGas + gas[idx] - cost[idx]
        if currGas < 0:
            return -1

    return startIdx

if __name__ == "__main__":
    gas = [4,5,7,4]
    cost = [6, 6, 3, 5]
    print(startStation(gas, cost))

C#

using System;

class GfG {
    static int startStation(int[] gas, int[] cost) {
        int n = gas.Length;
        int startIdx = 0;

        // Initially tank is empty
        int currGas = 0;

        for (int i = 0; i < n; i++) {
            currGas = currGas + gas[i] - cost[i];

            // If currGas becomes less than zero, then
            // It's not possible to proceed with this startIdx
            if (currGas < 0) {
                startIdx = i + 1;
                currGas = 0;
            }
        }

        // Check if startIdx can be a valid 
        // starting point for the Circular tour
        currGas = 0;
        for (int i = 0; i < n; i++) {

            // Circular Index
            int idx = (i + startIdx) % n;
            currGas = currGas + gas[idx] - cost[idx];
            if (currGas < 0)
                return -1;
        }

        return startIdx;
    }

    static void Main() {
        int[] gas = { 4,5,7,4};
        int[] cost = {6, 6, 3, 5 };
        Console.WriteLine(startStation(gas, cost));
    }
}

JavaScript

function startStation(gas, cost) {
    let n = gas.length;
    let startIdx = 0;

    // Initially tank is empty
    let currGas = 0;

    for (let i = 0; i < n; i++) {
        currGas = currGas + gas[i] - cost[i];

        // If currGas becomes less than zero, then
        // It's not possible to proceed with this startIdx
        if (currGas < 0) {
            startIdx = i + 1;
            currGas = 0;
        }
    }

    // Checking if startIdx can be a valid 
    // starting point for the Circular tour
    currGas = 0;
    for (let i = 0; i < n; i++) {

        // Circular Index
        let idx = (i + startIdx) % n;
        currGas = currGas + gas[idx] - cost[idx];
        if (currGas < 0)
            return -1;
    }

    return startIdx;
}

// driver code
let gas = [4,5,7,4];
let cost = [6, 6, 3, 5];
console.log(startStation(gas, cost));

Output

[Expected Approach 2] Greedy Approach in One Pass - O(n) Time and O(1) Space

This approach is an optimization of the previous one. After completing a full traversal of the array, instead of checking validity by circularly traversing from the starting index, we calculate the total remaining gas (the net difference between gas and cost). If this difference is greater than or equal to zero, the starting point is valid; otherwise, completing a circular loop is not possible.

C++

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

int startStation(vector<int> &gas, vector<int> &cost) {
  	int n = gas.size();  
  
    // Variables to track total and current remaining gas
    int totalGas = 0;
    int currGas = 0;
    int startIdx = 0;

    // Traverse through each station to calculate remaining
    // gas in the tank, and total gas 
    for(int i = 0; i < n; i++) {
      	currGas += gas[i] - cost[i]; 
        totalGas += gas[i] - cost[i];  

        // If currGas is negative, circular tour can't 
      	// start with this index, so update it to next one
        if(currGas < 0) {
            currGas = 0;
            startIdx = i + 1; 
        }
    }

    // No solution exist
    if(totalGas < 0) 
        return -1;

    return startIdx;
}

int main() {
    vector<int> gas = {4,5,7,4};
    vector<int> cost = {6, 6, 3, 5};
    cout << startStation(gas, cost); 
    return 0;
}

C

#include <stdio.h>

int startStation(int gas[], int cost[], int n) {
  
    // Variables to track total and current remaining gas
    int totalGas = 0;
    int currGas = 0;
    int startIdx = 0;

    // Traverse through each station to calculate remaining
    // gas in the tank, and total gas
    for (int i = 0; i < n; i++) {
        currGas += gas[i] - cost[i];
        totalGas += gas[i] - cost[i];

        // If currGas is negative, circular tour can't
        // start with this index, so update it to next one
        if (currGas < 0) {
            currGas = 0;
            startIdx = i + 1;
        }
    }

    // No solution exists
    if (totalGas < 0)
        return -1;

    return startIdx;
}

int main() {
    int gas[] = {4,5,7,4};
    int cost[] = {6, 6, 3, 5};
    int n = sizeof(gas) / sizeof(gas[0]);
  
    printf("%d\n", startStation(gas, cost, n));
    return 0;
}

Java

class GfG {
    static int startStation(int[] gas, int[] cost) {
        int n = gas.length;

        // Variables to track total and current remaining gas
        int totalGas = 0;
        int currGas = 0;
        int startIdx = 0;

        // Traverse through each station to calculate remaining
        // gas in the tank, and total gas
        for (int i = 0; i < n; i++) {
            currGas += gas[i] - cost[i];
            totalGas += gas[i] - cost[i];

            // If currGas is negative, circular tour can't
            // start with this index, so update it to next one
            if (currGas < 0) {
                currGas = 0;
                startIdx = i + 1;
            }
        }

        // No solution exists
        if (totalGas < 0)
            return -1;

        return startIdx;
    }

    public static void main(String[] args) {
        int[] gas = {4,5,7,4 };
        int[] cost = {6, 6, 3, 5};
        System.out.println(startStation(gas, cost));
    }
}

Python

def startStation(gas, cost):
    n = len(gas)
    
    # Variables to track total and current remaining gas
    totalGas = 0
    currGas = 0
    startIdx = 0
    
    # Traverse through each station to calculate remaining
    # gas in the tank, and total gas
    for i in range(n):
        currGas += gas[i] - cost[i]
        totalGas += gas[i] - cost[i]
        
        # If currGas is negative, circular tour can't
        # start with this index, so update it to next one
        if currGas < 0:
            currGas = 0
            startIdx = i + 1
    
    # No solution exists
    if totalGas < 0:
        return -1
    
    return startIdx

if __name__ == "__main__":
    gas = [4,5,7,4]
    cost = [6, 6, 3, 5]
    print(startStation(gas, cost))

C#

using System;

class GfG {
    static int startStation(int[] gas, int[] cost) {
        int n = gas.Length;
        
        // Variables to track total and current remaining gas
        int totalGas = 0;
        int currGas = 0;
        int startIdx = 0;

        // Traverse through each station to calculate remaining
        // gas in the tank, and total gas
        for (int i = 0; i < n; i++) {
            currGas += gas[i] - cost[i];
            totalGas += gas[i] - cost[i];

            // If currGas is negative, circular tour can't
            // start with this index, so update it to next one
            if (currGas < 0) {
                currGas = 0;
                startIdx = i + 1;
            }
        }

        // No solution exists
        if (totalGas < 0)
            return -1;

        return startIdx;
    }

    static void Main() {
        int[] gas = { 4,5,7,4 };
        int[] cost = {6, 6, 3, 5 };
        Console.WriteLine(startStation(gas, cost));
    }
}

JavaScript

function startStation(gas, cost) {
    const n = gas.length;

    // Variables to track total and current remaining gas
    let totalGas = 0;
    let currGas = 0;
    let startIdx = 0;

    // Traverse through each station to calculate remaining
    // gas in the tank, and total gas
    for (let i = 0; i < n; i++) {
        currGas += gas[i] - cost[i];
        totalGas += gas[i] - cost[i];

        // If currGas is negative, circular tour can't
        // start with this index, so update it to next one
        if (currGas < 0) {
            currGas = 0;
            startIdx = i + 1;
        }
    }

    // No solution exists
    if (totalGas < 0)
        return -1;

    return startIdx;
}

// Driver Code
const gas = [4,5,7,4];
const cost = [6, 6, 3, 5];
console.log(startStation(gas, cost));

Output

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem