Day 13 - Minimum Jumps.md

Difficulty	Medium
Source	160 Days of Problem Solving
Tags	Dynamic Programming Greedy Arrays

🚀 Day 13. Minimum Jumps 🧠

The problem can be found at the following link: Question Link

💡 Problem Description:

Given an array arr[] of non-negative integers, each element represents the maximum number of steps that can be taken forward from that index.

Find the minimum number of jumps required to reach the last index.
If the last index is not reachable, return -1.

🔍 Example Walkthrough:

Example 1:

Input:

arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]  

Output:

3  

Explanation:

• Jump from arr[0] = 1 → arr[1] = 3.
• Jump from arr[1] = 3 → arr[4] = 9.
• Jump from arr[4] = 9 → last index.

Example 2:

Input:

arr = [1, 4, 3, 2, 6, 7]  

Output:

2  

Explanation:

• Jump from arr[0] = 1 → arr[1] = 4.
• Jump from arr[1] = 4 → last index.

Example 3:

Input:

arr = [0, 10, 20]  

Output:

-1  

Explanation:

Since arr[0] = 0, we cannot move forward.

Constraints:

• $2 \leq \text{arr.size()} \leq 10^4$
• $0 \leq \text{arr[i]} \leq 10^4$

🎯 My Approach:

Greedy Approach

1. Track the farthest position reachable at every step.
2. Use a variable end to mark the last index reachable within the current jump.
3. If i reaches end, make a jump and update end.
4. If at any point i == end and end < n-1, return -1.

Algorithm Steps:

1. Initialize three variables:
   • jumps = 0 → Tracks the number of jumps.
   • farthest = 0 → Tracks the farthest reachable index.
   • end = 0 → Marks the end of the current jump.
2. Iterate through the array (except the last element):
   • Update farthest = max(farthest, i + arr[i]).
   • If i == end:
     • Increase jumps.
     • Update end = farthest.
     • If end >= n-1, return jumps.
3. If the last index is never reached, return -1.

🕒 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(N), as we iterate through the array only once.
• Expected Auxiliary Space Complexity: O(1), as we use only a few variables for tracking jumps and indices.

📝 Solution Code

Code (C++)

class Solution {
  public:
    int minJumps(vector<int>& arr) {
        int n = arr.size(), jumps = 0, farthest = 0, end = 0;
        if (n == 1) return 0;
        for (int i = 0; i < n - 1; i++) {
            farthest = max(farthest, i + arr[i]);
            if (i == end) {
                jumps++;
                end = farthest;
                if (end >= n - 1) return jumps;
            }
        }
        return -1;
    }
};

⚡ Alternative Approaches

2️⃣ Dynamic Programming (O(N²) Time, O(N) Space) — DP Approach

Algorithm Steps:

1. Use a 1D DP array dp[i], where dp[i] stores the minimum jumps needed to reach index i.
2. Base Case:
   • dp[0] = 0 (0 jumps needed at the start).
   • Initialize dp[i] = INT_MAX for all i > 0.
3. Transition:
   • For every j < i, check if j can reach i (j + arr[j] ≥ i).
   • If yes, update dp[i] = min(dp[i], dp[j] + 1).
4. Return dp[n-1], or -1 if dp[n-1] is INT_MAX (unreachable).

class Solution {
  public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < n; i++)
            for (int j = 0; j < i; j++)
                if (j + arr[j] >= i && dp[j] != INT_MAX)
                    dp[i] = min(dp[i], dp[j] + 1);
        return dp[n-1] == INT_MAX ? -1 : dp[n-1];
    }
};

✅ Time Complexity: O(N²)
✅ Space Complexity: O(N)

3️⃣ BFS (O(N) Time, O(N) Space) — Optimal Approach

Algorithm Steps:

1. Use a queue to track the farthest reachable index in BFS style.
2. At each level, explore all possible jumps.
3. Use BFS levels as jump count:
   • Process all indices reachable from the current level before moving to the next.
   • When reaching the last index, return the number of jumps.

class Solution {
  public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        if (n == 1) return 0;
        queue<int> q;
        vector<bool> visited(n, false);
        q.push(0);
        visited[0] = true;
        int jumps = 0;
        while (!q.empty()) {
            int size = q.size();
            while (size--) {
                int i = q.front();
                q.pop();
                for (int j = 1; j <= arr[i]; j++) {
                    int next = i + j;
                    if (next >= n - 1) return jumps + 1;
                    if (!visited[next]) {
                        visited[next] = true;
                        q.push(next);
                    }
                }
            }
            jumps++;
        }
        return -1;
    }
};

✅ Time Complexity: O(N)
✅ Space Complexity: O(N)

Comparison of Approaches

Approach	⏱️ Time Complexity	🗂️ Space Complexity	✅ Pros	⚠️ Cons
Greedy (Optimized)	🟢 O(N)	🟢 O(1)	Fastest, simple, works in O(N)	Requires greedy intuition
Dynamic Programming	🟡 O(N²)	🟡 O(N)	Intuitive	Slower for large inputs
BFS Approach	🟢 O(N)	🔴 O(N)	Good for large inputs	Uses extra space

✅ Best Choice?

• For fast execution: Use Greedy Approach (O(N)).
• For structured approach: Use 1D DP (O(N²)).
• For handling larger inputs: Use BFS (O(N)).

Code (Java)

class Solution {
    static int minJumps(int[] arr) {
        int n = arr.length, jumps = 0, farthest = 0, end = 0;
        if (n == 1) return 0;
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(farthest, i + arr[i]);
            if (i == end) {
                jumps++;
                end = farthest;
                if (end >= n - 1) return jumps;
            }
        }
        return -1;
    }
}

Code (Python)

class Solution:
    def minJumps(self, arr):
        n, jumps, farthest, end = len(arr), 0, 0, 0
        if n == 1: return 0
        for i in range(n - 1):
            farthest = max(farthest, i + arr[i])
            if i == end:
                jumps += 1
                end = farthest
                if end >= n - 1: return jumps
        return -1

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count