Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
- 0 <= j <= nums[i] and
- i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Example:
Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Approach: My observation about the problem is if we can reach an index i and then we can definitely reach index i - 1. The proof is simple:
- If the length of jump is 1 then we are already at i - 1.
- Otherwise we can take length - 1 jump to reach i - 1.
In this way we can prove that we can reach any j where j = 0 to i - 1. Now we can maintain a table say jump where jump[i] tells the farthest point it can reach. We can fill this table in following way:
- jump[0] = nums[0]
- jump[i] = MAX(jump[i - 1], i + jump[i]
Now we can simply use this table to get our answer.
Implementation in C#:
public int Jump(int[] nums)
{
int length = nums?.Length ?? 0;
if(length <= 1)
{
return 0;
}
int[] jumps = new int[length];
jumps[0] = nums[0];
for (int i = 1; i < length; ++i)
{
jumps[i] = Math.Max(jumps[i - 1], i + nums[i]);
}
int numOfJumps = 0;
for (int i = 0; i < length - 1; i = jumps[i])
{
++numOfJumps;
}
return numOfJumps;
}
Complexity: O(n)
No comments:
Post a Comment