55. Jump Game

Stack (My Solution)

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[n]; // prevent visiting same index for multiple times
        
        stack.push(0);
        visited[0] = true;

        while (!stack.isEmpty()) {
            int pos = stack.pop();

            // reached or passed the last index
            if (pos >= n - 1) return true;

            // all blocks can be reached from the current index
            for (int i = 1; i <= nums[pos]; i++) {
                int next = pos + i;
                if (next < n && !visited[next]) {
                    visited[next] = true;
                    stack.push(next);
                }
            }
        }

        return false; // all failed
    }
}

Remarks:

1. TC: $O(n^2)$, SC: $O(n)$

Greedy

class Solution {
    public boolean canJump(int[] nums) {
        int farthest = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > farthest) return false;
            farthest = Math.max(farthest, i + nums[i]);
        }
        return true;
    }
}

Remarks:

1. TC: $O(n)$, SC: $O(1)$
2. Key point: The farthest reachable position is non-decreasing

Dynamic Programming

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[n - 1] = true; // we can always reach the final dest from the final dest

        for (int i = n - 2; i >= 0; i--) {
            int maxJump = Math.min(i + nums[i], n - 1); // avoid out of boundry
            for (int j = i + 1; j <= maxJump; j++) { // check the points taht i can reach.
                if (dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[0]; // from start can reach dest
    }
}

1. TC: $O(n^2)$, SC: $O(n)$