0062MediumArrayGreedy

Charge Loop Launch Pad

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_launch_pad(charge: list[int], drain: list[int]) -> int:

Java

public int findLaunchPad(int[] charge, int[] drain)

The intended approach

Time O(n)Space O(1)

The ring is only survivable at all when the charge collected over the whole ring covers the drain over the whole ring, so keep a running total of `charge[i] - drain[i]` to decide between an answer and `-1`. Alongside it keep the battery level for the stretch begun at the current candidate pad: the moment that level dips below zero, no pad inside that stretch can be the answer, so move the candidate to the next pad and reset the level. One pass leaves the candidate on the only pad that can work.

Pythonentry point: find_launch_pad

def find_launch_pad(charge, drain):
    surplus = 0
    tank = 0
    start = 0
    for i in range(len(charge)):
        delta = charge[i] - drain[i]
        surplus += delta
        tank += delta
        if tank < 0:
            start = i + 1
            tank = 0
    if surplus < 0:
        return -1
    return start

The obvious version

Place the drone on each pad in turn and simulate the whole ring hop by hop, abandoning a placement as soon as the battery would go negative. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_launch_pad(charge, drain):
    n = len(charge)
    for begin in range(n):
        tank = 0
        ok = True
        for step in range(n):
            pad = (begin + step) % n
            tank += charge[pad]
            tank -= drain[pad]
            if tank < 0:
                ok = False
                break
        if ok:
            return begin
    return -1

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in