Can the Frog Reach the Last Lily Pad?

Medium15–20 min

Topics

GreedyArrayDynamic Programming

Companies

AmazonMicrosoftAppleGoogle

A frog stands on the first of a row of lily pads. Each pad has a number: the longest hop the frog can make forward from that pad. From pad i it may hop to any pad from i + 1 up to i + hops[i]. Decide whether the frog can reach the last pad.

Working out, pad by pad, which pads are reachable by looking back at every earlier pad is quadratic. A simple greedy insight does it in one pass: the reachable pads always form a solid stretch starting at pad 0, so it is enough to remember how far that stretch extends.

Test Case 1:

Input:hops = [2, 2, 0, 0, 3, 1]

Output:false

Explanation:The frog can reach pads 1, 2 and 3 (pad 1 hops up to 2 pads: to pad 3). But pads 2 and 3 have hops of 0, and pad 1 reaches at most pad 3, so pad 4 — and the last pad — are out of reach.

Test Case 2:

Input:hops = [1, 1, 1, 1]

Output:true

Explanation:One pad at a time works: 0 → 1 → 2 → 3.

Test Case 3:

Input:hops = [0]

Output:true

Explanation:A single pad: the frog is already on the last pad.

Constraints

◆1 ≤ hops.length ≤ 15 and 0 ≤ hops[i] ≤ 8; hops[i] is the longest hop the frog can make from pad i
◆The frog starts on pad 0. From pad i it may hop forward to any pad from i + 1 up to i + hops[i] — any distance in that range, not only the maximum
◆A pad with hops[i] = 0 lets the frog go nowhere. Return true if the frog can reach the last pad, otherwise false

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Work Out Which Pads Are Reachable One by One

Brute

Build a table where reachable[p] says whether the frog can get to pad p. Pad 0 is reachable. For each later pad, look back at every earlier pad: if some pad is reachable and its longest hop reaches at least pad p, then p is reachable. The answer is reachable[n − 1]. It is correct, but every pad is compared with every earlier pad.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public boolean canReachLastPad(int[] hops) {
        int n = hops.length;
        boolean[] reachable = new boolean[n];
        reachable[0] = true;
        for (int pad = 1; pad < n; pad++) {
            for (int from = 0; from < pad; from++) {
                if (reachable[from] && from + hops[from] >= pad) {
                    reachable[pad] = true;
                    break;
                }
            }
        }
        return reachable[n - 1];
    }
}

Optimal — Track the Farthest Pad Any Reachable Pad Can Reach

Optimal

The set of reachable pads is always a solid stretch from pad 0 up to some farthest pad — if the frog can reach pad p, it can reach every pad before p on the way (it can hop shorter distances). So just remember that farthest reachable pad. Walk the pads in order: if you arrive at a pad beyond the farthest reachable one, the frog is stranded — return false. Otherwise extend the farthest reach with pad + hops[pad]. If the walk finishes, the last pad was reachable.

TimeO(n)

SpaceO(1)