45. Jump Game II

📝 Problem Details

• Title: 45. Jump Game II
• Link: https://leetcode.com/problems/jump-game-ii/
• Difficulty: Medium
• Tags/Categories: Greedy

input array nums of length n start of position nums[0] each nums[i] represents the max length of a forward jump from index i return the minimum number of jumps to reach nums[n-1]

💭What Were My Initial Thoughts?

initially thought of a DP approach when the question mentioned finding the **minimum** number of jumps

- this would be O(n^2) in time complexity
- instead, we can make a greedy choice at each step:
	- try to extend the farthest possible reach at each step
	- only increment the jump counter when you reach the end of your current jump range

- we do not jump at every index, instead we decide when to jump based on how far we can reach
- a jump is make only when we reach the "edge" of our current range (the farthest index we could reach with the previous jump)
- track the farthest index we can reach sa we iterate through the array

💡 Explanation of Solution

- init:
	- jumps = 0      --> (count of jumps made)
	- currEnd = 0    --> (end of current jump range)
	- farthest = 0   --> (farthest index reachable in next jump)

- iterate over nums (except for the last index)
	- update farthest = max(farthest, i + nums[i])
		- update how far we can reach from the current position
	- if i reaches currEnd, we should jump
		- increment jumps
		- update currEnd = farthest (move to the next range)

- return jumps

⌛ Complexity Analysis

Time Complexity: O(n)
Space Compleixty: O(1)

💻 Implementation of Solution

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return 0; // edge case: already at the last index
    
        int jumps = 0;
        int currEnd = 0;
        int farthest = 0;
 
        for(int i = 0; i  < nums.size()-1; i++) { // dont need to check the last index
            farthest = max(farthest, i + nums[i]);
            
            if(i == currEnd) { // when we reach the current boundary, jump
                jumps++;
                currEnd = farthest; // move the boundary
            }
 
            if(currEnd >= n-1) break; // if we can reach the last index, stop early
        }
 
        return jumps;
    }
};