Jump Game Iii - Leetcode Solution

Problem Statement:

Given an array of non-negative integers arr, start from the position start and reach the last index of the array. You can jump to any index that is equal to or less than the maximum index you can reach in the current position. At any index, you must go forward. Determine if you can reach the last index.

Example:

Input: arr = [4,2,3,0,3,1,2], start = 5 Output: true Explanation: All possible ways to reach at the last index are: Index 5 -> Index 4 -> Index 1 -> Index 2 -> Index 3 -> Index 6 -> Index 7 Index 5 -> Index 6 -> Index 4 -> Index 1 -> Index 2 -> Index 3 -> Index 6 -> Index 7

Solution:

This problem can be solved by using BFS (Breadth-first Search) algorithm. We will start from the given start index and consider all possible positions that we can jump to. We will add these positions to a queue and then take one position at a time from the queue and repeat the same process for that position. We will also maintain a visited array to keep track of the visited positions so that we don't visit them again.

Algorithm:

1. Initialize a queue with start index and visited array with false values for all indices.
2. Run a loop until queue is not empty.
3. Dequeue the next index from the queue.
4. If the dequeued index is equal to the last index, then return true.
5. Mark this index as visited in the visited array.
6. Calculate the maximum index that can be reached from this index.
7. For all possible indices that can be reached, check if they are not visited and add to queue.
8. If the loop finishes and last index is not reached, then return false.

Code:

class Solution { public boolean canReach(int[] arr, int start) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[arr.length];

    queue.offer(start);
    visited[start] = true;
    
    while(!queue.isEmpty()) {
        int index = queue.poll();
        if(arr[index] == 0) {
            return true;
        }
        int left = index - arr[index];
        int right = index + arr[index];
        if(left >= 0 && !visited[left]) {
            queue.offer(left);
            visited[left] = true;
        }
        if(right < arr.length && !visited[right]) {
            queue.offer(right);
            visited[right] = true;
        }
    }
    return false;
}

}

Complexity Analysis:

The time complexity of this algorithm is O(n) where n is the length of the input array. Because in the worst-case scenario, we might end up exploring all indices of the array.

The space complexity of this algorithm is O(n) because we are using a boolean visited array of size n and a queue to store at most n elements.

1