Java - Gas Station Problem

Problem Statement

You have N gas stations arranged in a circular route. You are given two integer arrays:

gas[i]: Amount of gas available at station i.

cost[i]: Amount of gas required to travel from station i to station (i+1).

Find the starting gas station index (0-based) from where you can complete a full circuit without running out of gas. If not possible, return -1.

Example

Input

gas  = {1, 2, 3, 4, 5};

cost = {3, 4, 5, 1, 2};

Output

Starting Gas Station Index: 3

Explanation

Start at index 3: Gas = 4, travel to 4 → Gas Left = (4 - 1) + 5 = 8

Travel to 0 → Gas Left = (8 - 2) + 1 = 7

Travel to 1 → Gas Left = (7 - 3) + 2 = 6

Travel to 2 → Gas Left = (6 - 4) + 3 = 5

Travel to 3 → Gas Left = (5 - 5) + 4 = 4 ✅ (Completed)

Approach

Greedy Approach (O(N))

Calculate the total gas available and total cost.

If total_gas < total_cost, return -1 (not possible).

Start from 0, track gas balance.

If at any point, current_gas < 0, reset the start index.

Set start = i+1 and reset current_gas = 0.

Java Code

public class GasStation {

    public static int canCompleteCircuit(int[] gas, int[] cost) {

        int totalGas = 0, totalCost = 0, start = 0, currentGas = 0;

        for (int i = 0; i < gas.length; i++) {

            totalGas += gas[i];

            totalCost += cost[i];

            currentGas += gas[i] - cost[i];

            if (currentGas < 0) { // Can't continue from this station

                start = i + 1;

                currentGas = 0;

            }

        }

        return (totalGas >= totalCost) ? start : -1;

    }

    public static void main(String[] args) {

        int[] gas = {1, 2, 3, 4, 5};

        int[] cost = {3, 4, 5, 1, 2};

        int result = canCompleteCircuit(gas, cost);

        System.out.println("Starting Gas Station Index: " + result);

    }

}

Time Complexity

O(N) (Single loop for gas balance calculation)

Example Walkthrough

Input

int[] gas  = {2, 3, 4};

int[] cost = {3, 4, 3};

Output

Starting Gas Station Index: -1