[Top Interview 150] 45. Jump Game II

Solution)

class Solution:
    def jump(self, nums: List[int]) -> int:
        # Initialization
        step, l, r = 0, 0, 0

        # while the end of nums is not reached
        while r < len(nums)-1:
            farthest = 0

            # Find the farthest index that can be jumped from each window
            for i in range(l, r+1):
                farthest = max(farthest, nums[i]+i)
            
            # Slide window
            l = r+1
            r = farthest

            # Increment each jump
            step += 1
        
        return step

 
 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(n)
Space Complexity: O(1)

Explanation)

Today's solution is referenced from NeetCode. Check his video as well!
 
We'll find the minimum number of jumps it takes to reach the end, not the exact path.
 
For example, if nums is [2, 3, 1, 1, 4]
 
The minimum jumps it requires is 2.
The exact path would be index-wise, 0 -> 1 -> 4.
 
There is a difference and it's much easier to just find the minimum jumps.
 
From each jump, we'll figure the farthest it can reach. 
Then, we'll set a window using that information.
 
Regarding the nums above, if we start from 0th index, the left of window will be 1st index, and the right of window will be the farthest a 0th index can reach, which is 2nd index. 
 
Repeat this process of sliding the window and finding the farthest reach until the end of nums is reached.
 
 

Initialization)

Have a variable that will save steps/jumps to reach next window. 
 
left and right sides of window will initially be zero as we start from 0th index.
 

def jump(self, nums: List[int]) -> int:
        step, l, r = 0, 0, 0

 
 

Find the Farthest)

Variable farthest will save the farthest index each window can reach.
 
Then, through a for loop that iterates the window, we'll find the farthest index.
 
Once the farthest index that each window can reach is found, we'll slide the window.
left would become right+1 and right would become farthest. 
 
Since we moved the window, meaning we jumped from a previous window, we need to increment step.
 
This while loop will be continued until the right side of window reaches the end of nums. Thus if the while loop ends, meaning the window reached the end of nums, we'll return the minimum jump.
 

def jump(self, nums: List[int]) -> int:
        step, l, r = 0, 0, 0

        while r < len(nums)-1:
            farthest = 0

            for i in range(l, r+1):
                farthest = max(farthest, nums[i]+i)
            
            l = r+1
            r = farthest

            step += 1
         
        return step

 
 
 
I first thought I needed to find an exact minimum length of path to reach the end of nums. Since it was a follow-up problem of a previous problem, I wanted to solve this by myself but I guess I need more practice :)