Jump Game II
Updated
Problem statement
You are given an integer array nums of length n. You start at index 0.
The value nums[i] is the longest jump you can make forward from index i. From index i you can jump to any index from i + 1 up to i + nums[i], as long as it is inside the array. If nums[i] is 0, you cannot move from index i.
Return the smallest number of jumps needed to reach the last index, n - 1. If you already stand on the last index, the answer is 0.
Function
jump(nums: int[]) → intExamples
Example 1
nums = [2,3,0,1,4]return = 2From index 0 you can reach index 1 or index 2. Index 2 holds 0, so you would be stuck there.
Jump to index 1 instead. Its value is 3, so the next jump reaches index 4, the last index. That is 2 jumps. One jump is not enough, because index 0 reaches only up to index 2.
Example 2
nums = [4,1,1,3,1,1,1]return = 2The longest first jump lands on index 4. From there you can only move one step at a time, so that path needs 3 jumps.
A shorter first jump to index 3 is better. Its value is 3, so the second jump reaches index 6, the last index. The answer is 2.
Example 3
nums = [0]return = 0The array has one element, so index 0 is already the last index. No jump is needed.
Constraints
1 <= nums.length <= 100000 <= nums[i] <= 1000- The last index can always be reached from index
0.
More Tripjack Onsite Interview questions
Similar questions at other companies
- Best Time to Buy and Sell Stock IIKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Maximum Stock Profit with Unlimited TransactionsSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Jump Game IIOracle · ONSITE INTERVIEWOracle interview questions
- Maximum Stock Profit with Transaction LimitsMeta · ONSITE INTERVIEWMeta interview questions
- First Five Increasing Temperature RangesAmazon · ONSITE INTERVIEW
- Return a Minimum-Coin Change BreakdownDatadog · PHONE SCREEN · ONSITE INTERVIEWDatadog interview questions
- Most Transactions Kept Without Going NegativeDocuSign · ONSITE INTERVIEWDocuSign interview questions
- Best Time to Buy and Sell Stock IIHeadlands Technologies · ONSITE INTERVIEWHeadlands Technologies interview questions
- Fewest Jumps to the Last IndexC3.ai · ONSITE INTERVIEWC3.ai interview questions
- Jump GameBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions