Reachability

What is this?

Reachability asks a simple question: starting where you are, can you get to the goal, and if so in how few moves? The greedy trick is to track only the farthest spot you could possibly reach so far, like keeping your eye on the edge of how far you can see rather than mapping every street. You sweep forward once, always grabbing the longest reach available, and the answer falls out.

💡 Fun fact: Counting the minimum jumps to the end is secretly a breadth-first search in disguise. Each greedy reach is one BFS level, so you get the shortest path without ever building an actual queue of positions.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: to know whether you can get somewhere — or in how few moves — you rarely need to explore every path. Carry the farthest position you can currently reach, extend it greedily as you scan, and the question of reachability answers itself in one pass.

The pattern

Each problem walks forward while maintaining the boundary of what is reachable. The greedy claim is that always reaching as far as possible never hurts: a longer reach can only ever help.

• Track the farthest reach. Scan left to right keeping the maximum index you can reach from anything seen so far. If your current position ever exceeds that frontier, you are stuck; if the frontier covers the goal, you arrive.
• Level jumps for minimum steps. When you want the fewest moves, treat reach as BFS levels: the current jump covers a window, and you only increment the step count when you exhaust that window and must commit to the next farthest reach.
• Two-pointer subsequence cover. When you must cover a target by repeatedly consuming a source, greedily match as much of the target as possible per pass with two pointers, counting how many passes it takes.

The common thread: a frontier you push outward greedily, never second-guessing a reach that only widens your options.

The problems

Jump Game — from each index you may jump up to its value. Track the farthest reachable index as you scan; if you ever stand beyond it you cannot proceed, and if the frontier reaches the last index you can finish.

Jump Game II — now count the minimum jumps. Treat each jump as a BFS level covering a window of indices; extend the next reachable boundary across the window, and increment the step count only when you cross the current boundary's edge.

Shortest Way to Form String — build the target as a sequence of subsequences of the source. With two pointers, scan the source once per pass consuming as much of the target as it can; the number of passes is the answer, and an unmatchable character means it is impossible.

Key takeaways

1. Reachability is a frontier problem — track the farthest point you can reach and extend it greedily.
2. If your position ever passes the frontier, you are stuck; if the frontier covers the goal, you arrive.
3. For minimum moves, treat reach as BFS levels and only count a step when you exhaust the current window.
4. Greedy works here because a longer reach can never hurt — it only adds options.
5. Two-pointer greedy matching covers a target with the fewest subsequence passes.