Leetcode 55. Jump Game

55. Jump Game

Medium, Dynamic Programming

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.

 

Example 1:

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

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

 

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

Here's a simple explanation of each approach for solving the Jump Game problem:

Problem Understanding:

You are given an array nums where each element represents the maximum number of steps you can jump forward from that position. The task is to determine if you can reach the last index starting from the first index.

1. Greedy Approach

Explanation:
In the greedy approach, we track the farthest position we can reach from the current position. We start at the first index and keep updating the farthest index we can reach. If at any point the current index exceeds the farthest reachable index, it means we can't move forward, and thus, we return false. Otherwise, if we can reach the last index (or beyond), we return true.

Steps:

• Initialize a variable farthest as 0, which represents the farthest index we can reach.
• Iterate through the array. If the current index is greater than farthest, return false (since we can't reach this index).
• For each index, update the farthest index we can reach by taking the maximum of farthest and i + nums[i] (current index + the maximum jump length).
• If we reach the last index or beyond, return true.

Code:

public class Solution {
    public bool CanJump(int[] nums) {
        int farthest = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (i > farthest) return false; // Can't reach this index
            farthest = Math.Max(farthest, i + nums[i]);
        }
        return true;
    }
}

• Time Complexity: $O(n)$ — We go through the array once.
• Space Complexity: $O(1)$ — Only a constant amount of space is used.

---

2. Dynamic Programming Approach (Bottom-Up)

Explanation:
In this approach, we maintain a boolean array dp where dp[i] is true if we can reach the last index starting from index i. We work backwards from the last index, marking which indices can reach the end. If dp[0] is true at the end, it means we can reach the last index starting from the first one.

Steps:

• Create a dp array with dp[n-1] = true (since the last index can always reach itself).
• Loop through the array from right to left. For each position, check if we can reach the end by looking at positions we can jump to (using the value in nums[i]).
• If any position can reach the end, mark it as true in the dp array.
• Finally, check if dp[0] is true to see if we can reach the last index from the first index.

Code:

public class Solution {
    public bool CanJump(int[] nums) {
        int n = nums.Length;
        bool[] dp = new bool[n];
        dp[n - 1] = true; // Last index can always reach itself

        for (int i = n - 2; i >= 0; i--) {
            for (int j = 1; j <= nums[i] && i + j < n; j++) {
                if (dp[i + j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
}

• Time Complexity: $O(n^2)$ — We check all jumps from each index.
• Space Complexity: $O(n)$ — We use a dp array of size n.

---

3. Dynamic Programming Approach (Top-Down with Memoization)

Explanation:
This is a recursive approach with memoization. We start from the first index and try to recursively check if we can reach the last index. If we have already computed whether we can reach the end from a particular index, we store that result in a memoization array to avoid redundant calculations.

Steps:

• Use a recursive function to check if we can reach the last index starting from index i.
• For each index, recursively check if jumping to any of the next positions will allow us to reach the end.
• Store the result (true or false) for each index in a memoization array to avoid recalculating it.

Code:

public class Solution {
    public bool CanJump(int[] nums) {
        int n = nums.Length;
        int[] memo = new int[n];
        Array.Fill(memo, -1); // -1 = unknown, 0 = false, 1 = true
        
        bool Dfs(int i) {
            if (i >= n - 1) return true; // Reached or exceeded last index
            if (memo[i] != -1) return memo[i] == 1;
            
            for (int j = 1; j <= nums[i]; j++) {
                if (Dfs(i + j)) {
                    memo[i] = 1;
                    return true;
                }
            }
            memo[i] = 0;
            return false;
        }

        return Dfs(0);
    }
}

• Time Complexity: $O(n^2)$ — We recursively check all jumps.
• Space Complexity: $O(n)$ — Due to the recursion stack and memoization array.

---

Comparison of Approaches:

Approach	Time Complexity	Space Complexity	Explanation
Greedy	$O(n)$	$O(1)$	Most efficient solution, checks farthest reach.
DP (Bottom-Up)	$O(n^2)$	$O(n)$	Uses a bottom-up approach to fill a DP table.
DP (Top-Down)	$O(n^2)$	$O(n)$	Uses recursion with memoization to check if we can reach the end.

---

Summary:

• Greedy is the most efficient approach in terms of time and space complexity, as it runs in $O(n)$ time.
• Dynamic Programming (Bottom-Up) is easier to understand and works in $O(n^2)$ time but uses extra space for the DP array.
• Dynamic Programming (Top-Down) is more intuitive with recursion but also has $O(n^2)$ time complexity.

Let me know if you'd like any further details or explanations!