Loading problem...
You are navigating a stepping stone pathway represented by a 0-indexed integer array jumpCapacity of length n. Your journey begins at the first stone (index 0), and your goal is to reach the final stone (index n - 1) using the minimum number of hops.
Each element jumpCapacity[i] represents the maximum forward distance you can travel from stone i. Specifically, when standing on stone i, you may hop to any stone j where:
i < j ≤ i + jumpCapacity[i]j < n (you cannot hop beyond the pathway)Your objective is to determine the minimum number of hops required to travel from the starting stone to the destination. The input is guaranteed to have a valid path to the destination.
jumpCapacity = [2,3,1,1,4]2Starting at index 0, hop to index 1 (within the range allowed by jumpCapacity[0] = 2). From index 1, hop directly to index 4 (the destination) since jumpCapacity[1] = 3 allows reaching up to index 4. Total hops: 2.
jumpCapacity = [2,3,0,1,4]2From index 0, hop to index 1. From index 1, hop to index 4 (destination). Even though jumpCapacity[2] = 0, we bypass that stone entirely. Total hops: 2.
jumpCapacity = [3,2,2,1,0]2From index 0, hop to index 2 (or index 1). The optimal path is: 0 → 2 → 4 or 0 → 1 → 4. Either way, only 2 hops are needed to reach the destination.
Constraints