LC-1306 Medium LeetCode

1306. Jump Game III

Array Depth-First Search Breadth-First Search

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 66% Topics: Array, Depth-First Search, Breadth-First Search

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

import collections


class Solution(object):
    def canReach(self, arr, start):
        """
        :type arr: List[int]
        :type start: int
        :rtype: bool
        """
        q, lookup = collections.deque([start]), set([start])
        while q:
            i = q.popleft()
            if not arr[i]:
                return True
            for j in [i-arr[i], i+arr[i]]:
                if 0 <= j < len(arr) and j not in lookup:
                    lookup.add(j)
                    q.append(j) 
        return False

Solution from kamyu104/LeetCode-Solutions · MIT