Show problems as
Classic problem #134MediumArrayGreedy

Gas Station

Real-world version: Charge Loop Launch Pad
Tracked in this browser only
Read Gas Station on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey drone patrols n landing pads laid out on a ring and numbered 0 to n - 1. It always travels in ring order, and the hop out of pad n - 1 brings it back to pad 0.

Sitting on pad i tops the battery up by charge[i] units, and the hop from pad i to the pad after it burns drain[i] units. The drone is placed on a pad of your choosing with a flat battery, tops up there, and then hops from pad to pad until it lands back where it began. The battery is never allowed to fall below zero, so a hop it cannot afford is not permitted.

Return the number of the pad the drone must be placed on to finish the ring, or -1 when no pad works. The input is built so that at most one pad works.

Examples

Example 1

Input
charge = [3, 4, 4, 1, 3], drain = [5, 1, 3, 1, 4]
Output
1

Placed on pad 1 the drone tops up to 4 units and spends 1 to reach pad 2, and the battery reads 4, 4, 3 and 1 over the rest of the ring. Pad 0 is hopeless because 3 units cannot pay for a 5 unit hop, and every other placement runs flat before the ring closes.

Example 2

Input
charge = [3, 1, 2], drain = [4, 3, 1]
Output
-1

The ring burns 8 units in total but only offers 6, so the drone runs flat somewhere no matter where it is placed.

Example 3

Input
charge = [6], drain = [2]
Output
0

A single pad means one hop straight back to itself, and 6 units of charge covers the 2 units it costs.

Constraints

  • n == charge.length == drain.length
  • 1 <= n <= 10^5
  • 0 <= charge[i], drain[i] <= 10^4
  • The input is generated so that at most one starting pad completes the ring.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_launch_pad(charge: list[int], drain: list[int]) -> int:
Java
public int findLaunchPad(int[] charge, int[] drain)

More on the same topics