Problem statement

https://binarysearch.com/problems/Parity-Jump/

Solution

The idea is to create graph with reversed edges from our nums. Then we start from all even numbers with multi-source bfs and if we reach odd, update answer. Also we start from all odd numbers and when we reach even, update answer.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        n = len(nums)
        G = defaultdict(list)
        for i in range(n):
            if i + nums[i] < n: G[i + nums[i]] += [i]
            if i - nums[i] >= 0: G[i - nums[i]] += [i]

        odd_idx = [i for i in range(n) if nums[i] % 2 == 1]
        evn_idx = [i for i in range(n) if nums[i] % 2 == 0]
        ans = [-1] * n

        def bfs(nodes, p):
            queue = deque([(0, i) for i in nodes])
            V = set(nodes)
            while queue:
                dist, node = queue.popleft()
                if nums[node] % 2 == p: ans[node] = dist
                for w in G[node]:
                    if w in V: continue
                    V.add(w)
                    queue.append((dist + 1, w))

        bfs(odd_idx, 0)
        bfs(evn_idx, 1)
        return ans