[00:01] actually just a greedy problem. So, number is the maximum distance you can jump forward from that spot. Your job then is to find the minimum number of jumps needed to reach the last cell. The
[00:14] brute force idea is to try every possible path. From the first cell, branch into every cell you can land on. From each of those, branch again. The tree of possible paths expands exponentially, which is of course just
[00:26] way too slow. There's a much simpler greedy way. Think of it like this. After you could have landed on. Look across that whole range and find the single cell that lets you reach the farthest. That farthest spot becomes the new range
[00:40] you can reach with one more jump. Keep counting jumps until your range covers an example. We can start on the first cell. With one jump, we land anywhere up to index two. So, index zero through two is our first range. Scan it. The cell at
[00:55] index one carries us all the way to index four. That is the best reach in this range. Take jump two. Now, our new range stretches from index one to index four. Scan it again, and the cell at index four with value four shoots us
[01:09] well past the end. Take jump three. Our range now covers the last cell. The goal is reached. Three jumps total. In each step, we just scan the current range, pick the farthest reach, and extend it. No backtracking, no DP required. It's
[01:23] just one pass, O of N time, and O of one space. Try this and more problems with hellomaybe.com. Like, share, and subscribe.