55. Jump Game & 45. Jump Game II Leetcode Rust problem solution

We offer the best solutions for LeetCode problems in Rust. In this blog, we break down every problem’s solution with clear, step-by-step explanations.

Leetcode Problem : 55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Here’s the code again for reference:

rust

impl Solution {
    pub fn can_jump(nums: Vec<i32>) -> bool {
        let mut farthest = 0;
        for i in 0..nums.len() {
            if i > farthest {
                return false;
            }
            farthest = farthest.max(i + nums[i] as usize);
            if farthest >= nums.len() - 1 {
                return true;
            }
        }
        false
    }
}

Step-by-Step Explanation

1. Function Signature

pub fn can_jump(nums: Vec<i32>) -> bool

The function can_jump is a public method inside an impl Solution block (likely part of a struct Solution, though the struct isn’t shown here).
It takes a parameter nums, which is a vector of 32-bit integers (Vec<i32>), representing the jump distances at each index.
It returns a bool: true if you can reach the last index, false otherwise.

2. Variable Initialization

let mut farthest = 0;

farthest is a mutable variable initialized to 0. It keeps track of the farthest index you can reach at any point during the iteration.
At the start, you’re at index 0, so the farthest you can reach is index 0 (no jumps yet).

3. Loop Over the Array

for i in 0..nums.len() {

This is a for loop that iterates over the indices of the nums vector, from 0 to nums.len() – 1.
i represents the current position in the array.

4. Check if Current Index is Reachable

if i > farthest {
    return false;
}

At each step, check if the current index i is beyond the farthest index you can reach.
If i > farthest, it means you can’t reach the current position with any previous jumps, so you return false—it’s impossible to reach the end.

5. Update the Farthest Reachable Index

farthest = farthest.max(i + nums[i] as usize);

Calculate the maximum index you can reach from the current position: i + nums[i].
- nums[i] is the maximum jump distance from index i.
- i + nums[i] is the farthest index you could jump to from i.
Since nums[i] is an i32 and array indices in Rust are usize, we cast nums[i] to usize with as usize.
Update farthest to the maximum of its current value and i + nums[i] using the max method.
- This ensures farthest always tracks the furthest reachable index so far.

6. Check if the Goal is Reached

if farthest >= nums.len() - 1 {
    return true;
}

If farthest is greater than or equal to the last index (nums.len() – 1), you can reach the end of the array.
Return true because the goal is achieved.
This check is done inside the loop, so you can exit early as soon as you know you can reach the end.

7. Default Return

false

If the loop completes without returning true, it means you never reached the last index.
Return false as the default case.

Example Walkthrough

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

Start at index 0, farthest = 0.
Jump 2 steps (farthest = 2).
From index 1, jump 3 steps (farthest = 4).
farthest >= last index, return true.

Example 2: nums = [3,2,1,0,4]

farthest = 0 → Jump to 3
farthest = 1 → Jump to 2
farthest = 2 → Jump to 1
farthest = 3 → Can’t move forward (nums[3] = 0)
Stuck before reaching 4, return false.

Time Complexity

O(n) (Linear scan through nums).

Leetcode problem : 45. Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

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].

Here’s the code again for reference: Rust

 impl Solution {
pub fn jump(nums: Vec) -> i32 {
let mut jumps = 0;
let mut current_end = 0;
let mut farthest = 0;


   for i in 0..nums.len() - 1 {
        farthest = farthest.max(i + nums[i] as usize);

        if i == current_end {
            jumps += 1;
            current_end = farthest;
        }
    }

    jumps
}
}

Here’s the explanation:

The Function

pub fn jump(nums: Vec<i32>) -> i32

This is a function called jump that takes a vector (list) of integers (nums) as input.
It returns an integer (i32), which is the minimum number of jumps needed to reach the last index.

Variables

let mut jumps = 0;
let mut current_end = 0;
let mut farthest = 0;

jumps: Counts how many jumps we need. Starts at 0.
current_end: The farthest point we can reach with the current number of jumps. Starts at 0 (first position).
farthest: The maximum distance we could reach with one more jump. Starts at 0.
mut means these variables can change as the code runs.

The Loop

for i in 0..nums.len() - 1 {

This loop runs from the first index (0) to the second-to-last index (nums.len() – 1).
We don’t need to check the last index because once we can reach it, we’re done.

Inside the Loop

Step 1: Update the Farthest Reach

farthest = farthest.max(i + nums[i] as usize);

nums[i] is how far we can jump from the current position i.
i + nums[i] is the farthest index we could land on if we jumped from i.
farthest.max(…) updates farthest to the larger value between its current value and i + nums[i].
as usize converts the number to a type that works with array indices (don’t worry about this too much—it’s a Rust detail).

Simple terms: We’re checking how far we could go if we took a jump from this spot and keeping track of the best (farthest) option.

Step 2: Decide When to Jump

if i == current_end {
    jumps += 1;
    current_end = farthest;
}

if i == current_end: If we’ve reached the farthest point we can go with our current jumps, we need to make a new jump.
jumps += 1: Add 1 to our jump count because we’re jumping now.
current_end = farthest: Update current_end to the farthest point we can reach with this new jump.

Simple terms: When we can’t go further without jumping, we jump to the best spot we found so far and keep going.

Return the Result

jumps

At the end, jumps is returned as the minimum number of jumps needed.

How It Works (Example)

Let’s say nums = [2, 3, 1, 1, 4]:

Goal: Reach index 4 (value 4) in the fewest jumps.
Each number tells us the max distance we can jump from that spot.

Step-by-Step:

i = 0 (value 2):
- farthest = max(0, 0 + 2) = 2 (we can reach index 2).
- current_end = 0, and i = 0, so:
  - jumps = 1.
  - current_end = 2 (we jump to index 2).
i = 1 (value 3):
- farthest = max(2, 1 + 3) = 4 (we can reach index 4).
- i != current_end (1 != 2), so no jump yet.
i = 2 (value 1):
- farthest = max(4, 2 + 1) = 4 (still max is 4).
- i == current_end (2 == 2), so:
  - jumps = 2.
  - current_end = 4 (we jump to index 4).
i = 3 (value 1):
- Loop stops here because i doesn’t go to the last index.

Result: jumps = 2. We jumped from 0 to 2, then 2 to 4.

This solution runs in O(n) time, making it efficient for LeetCode.