0% completed
Problem Statement
You are given an array nums
containing n
integers, where nums[i]
represents the maximum length of a forward jump you can make from index i
. You are initially positioned at nums[0]
.
Return the minimum number of jumps needed to reach from the start
to the end
of the array.
Examples
Example 1:
- Input: nums =
[2, 3, 2, 2, 1]
- Expected Output: 2
- Justification: Start at index 0 and jump to index 1 (jump size 1). Then, jump from index 1 to the end (jump size 3).
Example 2:
- Input: nums =
[1, 2, 3, 4, 5]
- Expected Output: 3
- Justification: Start at index 0, jump to index 1 (jump size 1). Then, jump to index 3 (jump size 2). Finally, jump to the end (jump size 2).
Example 3:
- Input: nums =
[2, 3, 1, 2, 4, 1]
- Expected Output: 3
- Justification: Start at index 0, jump to index 1 (jump size 1). Then, jump to index 4 (jump size 2). Finally, jump to the end (jump size 1).
Constraints:
- 1 <= nums.length <= 10<sup>4</sup>
- 0 <= nums[i] <= 1000
- It's guaranteed that you can reach nums[n - 1].
Solution
To solve this problem, we need to keep track of the farthest point we can reach with each jump and count how many jumps we need. The strategy is to iterate through the array while updating the farthest point we can reach. Whenever we reach the end of the current jump range, we increment our jump count and update the current jump range to the farthest point we can reach. This method ensures that we use the fewest jumps possible to get to the end.
This approach works effectively because it uses a greedy algorithm to always make the optimal choice at each step. By focusing on the farthest reachable point, we minimize the number of jumps needed.
Step-by-Step Algorithm
-
Initialize Variables:
- Create a variable
jumps
and set it to 0. This will count the number of jumps needed. - Create a variable
currentEnd
and set it to 0. This will mark the end of the range for the current jump. - Create a variable
farthest
and set it to 0. This will track the farthest point that can be reached.
- Create a variable
-
Loop Through the Array:
- Iterate through the array from the first element to the second-to-last element (from index 0 to n-2):
- Update
farthest
to be the maximum offarthest
and the current index plus the jump length at that index (farthest = max(farthest, i + nums[i])
). - If the current index is equal to
currentEnd
:- Increment the
jumps
count (jumps++
). - Update
currentEnd
to befarthest
(currentEnd = farthest
).
- Increment the
- Update
- Iterate through the array from the first element to the second-to-last element (from index 0 to n-2):
-
Return Result:
- After the loop ends, return the value of
jumps
as the result.
- After the loop ends, return the value of
Algorithm Walkthrough
Using the input nums = [2, 3, 1, 2, 4, 1]
.
Initialization:
jumps = 0
currentEnd = 0
farthest = 0
Iteration 1:
- Index
i = 0
farthest = max(0, 0 + 2) = 2
- Since
i == currentEnd
(0 == 0):jumps++
(jumps = 1)currentEnd = farthest
(currentEnd = 2)
Iteration 2:
- Index
i = 1
farthest = max(2, 1 + 3) = 4
i != currentEnd
(1 != 2), so do nothing
Iteration 3:
- Index
i = 2
farthest = max(4, 2 + 1) = 4
- Since
i == currentEnd
(2 == 2):jumps++
(jumps = 2)currentEnd = farthest
(currentEnd = 4)
Iteration 4:
- Index
i = 3
farthest = max(4, 3 + 2) = 5
i != currentEnd
(3 != 4), so do nothing
Iteration 5:
- Index
i = 4
farthest = max(5, 4 + 4) = 8
- Since
i == currentEnd
(4 == 4):jumps++
(jumps = 3)currentEnd = farthest
(currentEnd = 8)
Return Result:
- Return
jumps
which is 3.
Code
Complexity Analysis
- Time Complexity: The algorithm runs in O(n) time, where
n
is the length of the array. This is because we iterate through the array once, and each operation inside the loop (like updating the farthest point) takes constant time. - Space Complexity: The algorithm uses O(1) additional space since we are only using a few extra variables (jumps, currentEnd, and farthest) regardless of the input size.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible