LeetCode Challenge: 45. Jump Game II - JavaScript Solution 🚀

Top Interview 150

Jumping through arrays with minimal effort is a classic problem that challenges your algorithmic thinking. Let's tackle LeetCode 45: Jump Game II, which asks us to find the minimum number of jumps required to reach the last index.

---

🚀 Problem Description

You are given an integer array nums of length n.

Each element nums[i] represents the maximum length of a forward jump from index 𝑖. Return the minimum number of jumps required to reach nums[n - 1]. It’s guaranteed that you can always reach the last index.

---

💡 Examples

Example 1

Input: nums = [2,3,1,1,4]  
Output: 2  
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2

Input: nums = [2,3,0,1,4]  
Output: 2  
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

---

🏆 JavaScript Solution

To solve this efficiently, we use a greedy approach to minimize the number of jumps by always jumping as far as possible within the current range.

Greedy Algorithm

var jump = function(nums) {
    let jumps = 0;
    let currentEnd = 0;
    let farthest = 0;

    for (let i = 0; i < nums.length - 1; i++) {

        farthest = Math.max(farthest, i + nums[i]);

        if (i === currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }

    return jumps;
};

---

🔍 How It Works

1. Track the farthest point:

   • As we iterate, calculate how far we can reach (farthest) using the current jump.

2. Trigger a jump:

   • Whenever we exhaust the range of the current jump (i === currentEnd), increment the jump counter and set the next range to the farthest point.

3. Stop at the last index:

   • The loop runs only until nums.length - 2, as we don’t need to jump beyond the last index.

---

🔑 Complexity Analysis

• > Time Complexity: O(n), where n is the length of the array. We traverse the array once.
• > Space Complexity: O(1), as no additional data structures are used.

---

📋 Dry Run

Input: nums = [2,3,1,1,4]

Output: 2

---

✨ Pro Tips for Interviews

1. Understand the greedy choice: Explain why jumping to the farthest reachable index minimizes total jumps.
2. Clarify constraints: Confirm with the interviewer that reaching the last index is always possible.
3. Edge cases:
   • Single-element array ([0] → 0 jumps).
   • Maximum jump length always greater than or equal to array length.

---

📚 Learn More

Check out the full explanation and code walkthrough on my Dev.to post:
👉 Jump Game - JavaScript Solution

What’s your approach to solving this problem? Let’s discuss below! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!