Reach the Last Cell

Medium

You have a row of cells, each holding a number: lengths[i] is the longest forward jump allowed from cell i. From cell i you may land on any cell from i + 1 to i + lengths[i] (if lengths[i] = 0, you are stuck there). You start on cell 0. Return True if you can reach the last cell and False otherwise.

Example 1

lengths=[1, 3, 0, 0, 2] → True

Jump from cell 0 to cell 1, then 3 forward straight to the last cell, 4.

Example 2

lengths=[2, 1, 0, 3] → False

Cells 0, 1 and 2 cannot get past cell 2, and its jump length is zero.

Example 3

lengths=[0] → True

We are already standing on the last cell.

Constraints

1 ≤ len(lengths) ≤ 10⁵
0 ≤ lengths[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium As Many Trades as You Like Medium Longest Seesaw Subsequence Medium Fewest Meetings to Cancel Medium Longest Chain of Segments Medium

Input

lengths=[1, 3, 0, 0, 2]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 69 tests on the server, hidden ones included.