cf.completefrontend
GREEDY & INTERVALS · CORE

Farthest-reach greedy

Walk a line of positions while tracking the farthest position you can reach so far, to decide if (or how quickly) you can get to the end.

Time O(n)Space O(1)5 practice problemsStep-through picture

The idea

Picture a row of stepping stones. From stone i you may jump forward up to jumps[i] stones. Can you get from the first stone to the last one? Trying every path of jumps could take forever, because the number of paths grows very fast.

The greedy idea is to keep one number: farthest, the farthest stone you know you can reach. Walk the stones in order. If you're standing on stone i and i is within farthest, you could have reached it, so stretch farthest to i + jumps[i] if that's further. If you ever arrive at a stone beyond farthest, no path can get there, and the answer is no.

The same walk counts the fewest jumps too: think of the stones you can reach with one jump as a level, then the stones you can reach with two jumps, and so on. It also solves covering problems, like the fewest video clips that cover a whole timeline.

An everyday example

Crossing a river on stepping stones

You walk across a river on a line of stones. Each stone has a number painted on it: how far you can leap from there. You walk from stone to stone and keep a mental note of the farthest stone any leap so far could land on. As long as the stone under your feet is within that note, you're fine. If you reach a stone past the note, there's no way you could have got there.

How the example maps to the code
In the exampleIn the code
The stone you're oni
The number painted on itjumps[i]
The farthest stone any leap so far can land onfarthest
A stone past your notei > farthest
Your note reaches the far bankfarthest >= jumps.length - 1

From the slow way to farthest-reach greedy

  1. The obvious way is to try every path. From index 0, try every jump length from 1 to jumps[0], then do the same from every landing spot. The number of paths grows very fast: with 30 positions that each allow a jump of 1 or 2, there are 832,040 different paths from the first index to the last.
  2. Many of those paths land on the same index. Whether you reach index 5 by 0 → 2 → 5 or by 0 → 1 → 3 → 5, the future from index 5 is the same. So you only need to know which indexes can be reached, not how. A true or false per index, filled from left to right, does that in O(n^2) time.
  3. Look closely at that list: the reachable indexes always form one solid block starting at 0. A jump from index p can land anywhere from p + 1 to p + jumps[p], so it never skips an index it passes over. If you can reach some index, you can reach every index before it. So the whole list shrinks to one number, farthest, the end of the block.
  4. Walk i from left to right. If i is inside the block, stretch the block to i + jumps[i] when that's further. If i is past the block, nothing can land on it, and the answer is no. Stop early with yes once the block covers the last index. That loop is the farthest-reach greedy.

How it works

  1. Start with farthest = 0: so far you can only reach the first position.
  2. Walk i from left to right.
  3. If i > farthest, position i can't be reached, and nothing after it can either: return false.
  4. Otherwise, stretch the reach: farthest = Math.max(farthest, i + jumps[i]).
  5. If farthest reaches the last index, return true.
  6. For the fewest jumps: count a new jump each time i passes the end of the current jump's reach, and set the new reach to the farthest seen.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function canReachEnd(jumps) {
  2. let farthest = 0;
  3. for (let i = 0; i < jumps.length; i++) {
  4. if (i > farthest) return false;
  5. farthest = Math.max(farthest, i + jumps[i]);
  6. if (farthest >= jumps.length - 1) return true;
  7. }
  8. return true;
  9. }

How fast it is

TimeO(n)
Extra memoryO(1)

One pass over the positions with constant work each, and only farthest is stored.

  • Best caseO(1)

    The first jump already covers the end, like jumps = [9, 0, 0]: the loop returns true at i = 0.

  • Average caseO(n)

    Typical inputs walk a good part of the list before farthest reaches the end or a wall stops the walk.

  • Worst caseO(n)

    Every jump is small, like jumps = [1, 1, 1, 1, 1]: the loop visits every index but the last before returning true.

Common mistakes

  • Always jumping as far as possible from where you stand. The farthest single jump can land on a dead end; track the farthest reach over all positions you pass instead.
  • Forgetting the i > farthest check, so the walk steps over a wall of zeros as if it could be crossed.
  • For the fewest jumps, looping all the way to the last index and counting one jump too many when currentEnd lands exactly on it.
  • Trying every path with recursion and no memory of results, which takes exponential time.

When to use it

Look for these clues in a problem:

  • Each position says how far you can move from it, and the question asks if you can reach the end.
  • The question asks for the fewest jumps, hops, stops, or clips to reach or cover a target.
  • Ranges or segments must cover a line from 0 to T with as few pieces as possible.
  • Trying every path would grow too fast, but only the farthest point matters at each step.

Check yourself

Answer each one in your head first, then open it.

Why can the walk stop for good as soon as i > farthest?

No earlier jump reaches index i or anything past it. An index nobody can stand on can't start a jump, so nothing from i onward can ever be reached.

What does the code return for [1, 0, 1], and at which i does it stop?

It returns false at i = 2. farthest reaches 1 at index 0, stays 1 at index 1, and then 2 > 1.

When does the return true after the loop run?

Only for an empty list. For any other list the loop returns inside: false at a wall, or true once farthest reaches jumps.length - 1, at the last index at the latest.

Why does a zero inside the block never hurt?

Math.max keeps farthest from shrinking. A zero only means you can't jump from that index, but other indexes in the block may jump past it.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule at the top of each loop: every index from 0 to farthest can be reached, and no jump from an index before i can land past farthest. At the start, farthest = 0 and no jumps have been used, so the rule is true.

Each step keeps it. If i <= farthest, index i is reachable, so every index from i + 1 to i + jumps[i] is reachable too, and stretching farthest adds exactly those. If i > farthest, then no earlier jump lands on i or beyond, and nobody can stand on i to jump from it, so no later index can ever be reached. Returning false is correct.

The loop returns true as soon as farthest covers the last index, which by the rule means the last index is reachable. Otherwise it returns false at the first index past the block. Since i grows by one each step, it runs at most n times.

Going deeper

3 more ideas

Why one number is enough

Every position from 0 to farthest can be reached. That's true at the start, and when you stand on a reachable i, every position from i to i + jumps[i] becomes reachable too, so stretching farthest keeps it true. Because the reachable positions always form one solid block from 0, knowing where the block ends tells you everything.

Counting the fewest jumps

Keep jumps, currentEnd (the farthest point reachable with the jumps counted so far), and farthest. Walk i up to the second-to-last index, stretching farthest. When i reaches currentEnd, you must jump again: add one to jumps and set currentEnd = farthest. This is a breadth-first search where each level is a block of positions, done in O(n) without a queue.

Why it takes O(n) time

Each position is visited once with constant work, and only one or two numbers are stored, so memory is O(1). Trying every path instead could take exponential time.

Work it by hand

Every step in a table, with why

Can you get from index 0 to index 6? Two zeros in a row look like a wall, but an earlier jump flies over them.

jumps = [2, 0, 3, 0, 0, 1, 4]

Stepijumps[i]i > farthesti + jumps[i]farthestWhat happensWhy
1020 > 0 is false22stretch to 2Index 0 is always reachable. From it, indexes 1 and 2 can be reached.
2101 > 2 is false12no changeIndex 1 is a dead end, since its jump is 0. That doesn't matter: index 2 is already in the block.
3232 > 2 is false55stretch to 5From index 2 you can reach up to index 5, past both zeros.
4303 > 5 is false35no changeA zero inside the block can't shrink it.
5404 > 5 is false45no changeThe second zero changes nothing either.
6515 > 5 is false666 >= 6: return truefarthest now covers the last index, 6, so the loop stops without looking at index 6.

It returns true after 6 steps. With jumps = [2, 0, 2, 0, 0, 1], the same walk gets stuck at farthest = 4 and returns false at i = 5, because 5 > 4.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Farthest-reach greedyO(n)O(1)Jumps only go forward and can land anywhere up to their length, and you need yes or no or the fewest jumps.
Dynamic programming over indexesO(n^2)O(n)Each index needs more than yes or no, like the cheapest total cost to land on it.
Breadth-first searchO(V + E)O(V)Moves aren't one solid forward range, such as jumps backward or to exact spots, so the reachable indexes can have holes.
Try every pathO(2^n)O(n)Never for real inputs. It only helps to state the problem.

Extra memory: O(1): one number, farthest, plus the loop index i.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Farthest-reach greedy and the other approaches, on a scale where each line up is 10 times more steps.
  • Farthest-reach greedy O(n)
  • Dynamic programming over indexes O(n^2)
  • Breadth-first search O(V + E)
  • Try every path O(2^n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Farthest-reach greedy101,0001 million
Dynamic programming over indexes1001 million1 trillion
Breadth-first search202,0002 million
Try every path1,024more than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
One position: jumps = [0]
At i = 0, farthest stays 0, and 0 >= 0 is true, so it returns true: you're already at the end.
An empty list: jumps = []
The loop never runs and the last line returns true. Decide whether an empty list makes sense for your problem; often it should be rejected first.
A zero at the start: jumps = [0, 4, 2]
At i = 0, farthest stays 0. At i = 1, 1 > 0, so it returns false. The big jump at index 1 never helps.
A wall of zeros with a long jump before it: jumps = [3, 0, 0, 1]
At i = 0, farthest becomes 3, the last index, so it returns true at once.
A huge jump value: jumps = [1e9, 0]
i + jumps[i] just makes farthest big, and farthest >= jumps.length - 1 returns true. No array of that size is ever made.

Variations and follow-ups

Twists interviewers add

Fewest jumps to the end

Think in levels: level 1 is every index one jump can reach, level 2 every index two jumps can reach, and each level is a block right after the one before. Walk i, keep farthest, and when i reaches the end of the current level, count one jump and make farthest the end of the next level. It's a breadth-first search without a queue, in O(n).

Walking backward from the goal

Walk from the right instead and keep goal, the leftmost index known to reach the end. If i + jumps[i] >= goal, move goal to i. The answer is goal === 0. It is the same O(n) idea seen from the other end.

Covering a timeline with clips

Clips [start, end] must cover [0, T] with as few clips as possible. For each start time, record the farthest end a clip starting there reaches; that is a jump table. The fewest-jumps walk then gives the answer, or finds a gap no clip covers.

Jumping both ways

If from i you may move to exactly i + jumps[i] or i - jumps[i], the reachable indexes no longer form one block. Use breadth-first search with a visited list instead: still O(n) time, but O(n) memory.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "each value is the most you can jump", "can you reach the last index", or "the fewest jumps". Forward moves of any length up to a limit are the clue.
  • Explain the key fact out loud: "the reachable indexes always form one solid block from 0, so I only track where the block ends". That sentence answers why one number is enough.
  • Point out the tempting wrong greedy: always taking the longest jump from where you stand. For jumps = [2, 3, 0, 0, 1], it jumps from 0 to 2 and gets stuck on a zero, while 0 → 1 → 4 works.
  • Test by hand: [0], a zero at the start of a longer list, and a wall of zeros that can and can't be jumped over. The usual follow-up is the fewest jumps: count a jump each time i reaches the end of the current level.

Where frontend code uses it

The same idea in real UI code
  • Keyboard navigation in a carousel where each slide may allow skipping ahead several slides: checking if the last slide is reachable is this same walk.
  • Choosing the fewest video segments or cached chunks that cover a whole timeline, such as the parts of a video that must be downloaded to play to the end.
  • Planning the fewest prefetch requests where each request covers a range of upcoming pages in a paginated list.

Related algorithms