Problem of The Day: Jump Game III

Problem Statement

leetcode problem link

BFS Approach [Accepted]

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        N = len(arr)
        graph = {i: [] for i in range(N)}
        for i, num in enumerate(arr):
            jump_forward = i + arr[i]
            jump_backward = i - arr[i]
            if jump_forward in graph:
                graph[i].append(jump_forward)
            if jump_backward in graph:
                graph[i].append(jump_backward)

        queue = deque()
        queue.append(start)
        visited = {start}
        while queue:
            node = queue.popleft()
            if arr[node] == 0:
                return True
            for nei in graph[node]:
                if nei not in visited:
                    queue.append(nei)
                    visited.add(nei)

        return False

Editorial Solution

Approach 1: Breadth-First Search

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        q = deque([start])

        while q:
            node = q.popleft()
            # Check if we reached zero
            if arr[node] == 0:
                return True
            if arr[node] < 0:
                continue

            # Check available next steps
            for i in [node + arr[node], node - arr[node]]:
                if 0 <= i < n:
                    q.append(i)

            # Mark as visited
            arr[node] = -arr[node]
        return False

Approach 2: Depth-First Search

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        if 0 <= start < len(arr) and arr[start] >= 0:
            if arr[start] == 0:
                return True

            arr[start] = -arr[start]
            return self.canReach(arr, start + arr[start]) or self.canReach(
                arr, start - arr[start]
            )

        return False