DEV Community

Cover image for LeetCode Challenge: 45. Jump Game II - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

2 1 1 1 1

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.
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

πŸ† 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;
};
Enter fullscreen mode Exit fullscreen mode

πŸ” 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]

Jump Game II
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

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here β†’

Top comments (1)

Collapse
 
rahulgithubweb profile image
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!

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

πŸ‘‹ Kindness is contagious

Please leave a ❀️ or a friendly comment on this post if you found it helpful!

Okay