Gas Station Problem

Gas Station Problem — ExecCode Easy DSA Practice

Solve the Gas Station problem on ExecCode. Free online easy DSA practice in Greedy. Write and run code in Java, C++, Python — no signup required to run.

Problem description

There are n gas stations along a circular route, where gas[i] is the fuel available at station i and cost[i] is the fuel needed to travel from station i to station i+1. Starting with an empty tank at some station, return the starting index that lets you travel the entire circuit once, or -1 if it is impossible. The answer is guaranteed to be unique if it exists.

Examples

Input gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]; Output 3. Input gas = [2, 3, 4], cost = [3, 4, 3]; Output -1. Input gas = [5, 1, 2, 3, 4], cost = [4, 4, 1, 5, 1]; Output 4

Constraints

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

Practice Gas Station free on ExecCode. Browse DSA problems, topic map, and placement guides.