Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Dynamic programming

Can you reach the last position?

Medium · Target 15 minutes · Dynamic programming · Type asked atAmazonMicrosoft

You start at position 0 of a list nums. From position i you may jump forward by any distance from 1 to nums[i]. Return true if you can reach the last position.

Examples

InputOutputWhy
nums = [2,3,1,1,4]true0 → 1 → 4.
nums = [3,2,1,0,4]falseEvery route lands on position 3, whose jump is 0.
nums = [0]trueAlready at the last position.

Constraints

  • 1 ≤ nums.length ≤ 10⁴
  • 0 ≤ nums[i] ≤ 10⁵

Hints

Hint 1

good[i] = can the end be reached from i. good[n − 1] = true.

Hint 2

good[i] = some j in i + 1 .. i + nums[i] has good[j].

Hint 3

Better: going right to left, track the leftmost good position; i is good if i + nums[i] reaches it.

Where people lose marks

  • Jumping exactly nums[i] instead of up to nums[i].
  • An O(n²) DP that times out on long lists with large jumps.
Console⌘/Ctrl + Enter runs

Write a solution and run it against the real test table.


Keep going

Preparing for a real process? Quant interview preparation, or book a free 20-minute call.