Gas Station in Java: Explanation & Practice

Problem summary

There are n gas stations in a circle. gas[i] is the gas at station i, cost[i] is the cost to travel to next station. Find the starting station to complete the circuit, or -1 if impossible.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        
        // If total gas >= total cost, solution exists
        // Track current tank; if negative, start from next station
        // Print: Start: 3
    }
}

Expected output and test cases

• [1,2,3,4,5] gas, [3,4,5,1,2] cost

  Start: 3

• [2,3,4] gas, [3,4,3] cost → impossible

  Start: -1

• Can start from beginning

  Start: 0

Hints

1. If total gas < total cost, no solution exists
2. If solution exists, there's exactly one starting point
3. Reset start whenever tank goes negative
4. The last reset position + 1 is the answer

Related Data Structures & Algorithms exercises

• Practice Jump Game in Java
• Practice Activity Selection (Interval Scheduling) in Java
• Practice Partition Labels in Java

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler