This practice workspace is built for desktop. Open it on a larger screen to start solving.

Gas Station

Greedy Algorithms·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 a solution exists, it is guaranteed to be unique.

Examples

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

Output: 3

Start at station 3 (gas = 4). Travel to station 4 with tank = 0 + 4 - 1 = 3. Travel to station 0 with tank = 3 + 5 - 2 = 6. Travel to station 1 with tank = 6 + 1 - 3 = 4. Travel to station 2 with tank = 4 + 2 - 4 = 2. Travel to station 3 with tank = 2 + 3 - 5 = 0. Therefore, return 3 as the starting index.

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

Output: -1

You can't start at station 0 or 1 (not enough gas to travel to the next station). Starting at station 2 still fails because you cannot return.

Constraints

n == gas.length == cost.length
1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4
The tests are generated such that a solution, if it exists, is unique.

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Greedy Algorithms
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.