Fewest Jumps to the Last Index
Updated
Problem statement
You are given an integer array jumps. You start on index 0.
From index i, one move takes you forward to any index from i + 1 up to i + jumps[i]. You may move fewer steps than jumps[i], but never backward. A value of 0 means you cannot move from that index.
Return the fewest moves needed to stand on the last index, jumps.length - 1. If the array has only one index, you are already there and the answer is 0.
Function
fewestJumps(jumps: int[]) → intExamples
Example 1
jumps = [1,4,2,1,0,3,1]return = 3From index 0 the only move is to index 1. From index 1 (value 4) you can reach indexes 2 to 5. Index 5 has value 3, so from there one more move reaches the last index, 6. That is 3 moves: 0 to 1, 1 to 5, 5 to 6. Two moves are not enough, because after the first move you can only be at index 1, and index 1 reaches at most index 5.
Example 2
jumps = [0]return = 0There is only one index, so you are already on the last index. No move is needed.
Example 3
jumps = [4,1,1,3,1,1,1]return = 2From index 0 you can reach indexes 1 to 4. Moving the full 4 steps to index 4 (value 1) still needs two more moves, 4 to 5 and 5 to 6, for 3 in total. A shorter move to index 3 (value 3) is better: from index 3 you reach the last index, 6, directly. The answer is 2.
Constraints
1 <= jumps.length <= 10^40 <= jumps[i] <= 1000- The last index can always be reached from index
0.
More C3.ai interview questions
- Every Result of Grouping an ExpressionONSITE INTERVIEW · Seen Jan 2023
- Rotate a Square Grid ClockwiseONSITE INTERVIEW · Seen Jan 2023
- Movie Schedule for Maximum EnjoymentONSITE INTERVIEW · Seen Jan 2023
- Days Until a Warmer DayPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Can All Courses Be FinishedONSITE INTERVIEW · Seen Nov 2021
- Longest Arithmetic SubsequenceONSITE INTERVIEW · Seen Feb 2021
- Gas Station LoopONSITE INTERVIEW · Seen Dec 2020
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024
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
- Jump Game IITripjack · ONSITE INTERVIEWTripjack 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
- Jump GameBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions