Reach zero

Problem Statement

You are given an array of integers of size $n$ and a starting index. Your task is to determine whether or not there the array contains a 0 that is “reachable” from the starting index. The array is not guarenteed to contain the integer 0.

An element $x$ can reach an element $y$ if $y$ is exactly $x$ elements to the left or the right of element $x$ . For example, in an array [2, 4, 1, 3, 6, 9], the element 1 can reach both 4 and 3 because they are each exactly one element away. If the element’s reach extends beyond the indices of the array, its reach does not wrap around. For example, the element 3 cannot reach any elements to its right.

Design an algorithm that will return a boolean indicating whether or not a 0 is reachable in the array.

Test Cases

Test Case 1

Input: [3, 2, 4, 5, 0, 1, 2, 9, 3], starting index: 0 Output: True

Test Case 2

Input: [2, 3, 5, 3, 8, 3, 0, 3, 5, 1, 3], starting index: 2 Output: False

Test Case 3

Input: [2, 3, 1, 4, 1, 4], starting index: 1 Output: False

Hints

Click Here

What happens on an input array of [1,1]? How can you ensure your algorithm ends?

Follow up question:

What is the runtime of this algorithm?

Click Below to see the Solution

Algorithm

The idea is to use recursion to determine whether each decision (traversing left or right) ever reaches 0. If at any point we have traversed all of the elements or are checking the same element twice, then we know the path we have taken so far is invalid.

Code


def _reachZero(arr, start):
	# the visited array keeps track of which indices we've visited so we don't recheck
	# indices and get into an infinite loop
	visited = [0] * len(arr)
	return reachZeroHelper(arr, start, visited)

def _reachZeroHelper(arr, start, visited):
	if (sum(visited) == len(arr)) or (start < 0) or (start > len(arr) - 1):
		return false
	if (arr[start] == 0):
		return true
	else:
		visited[start] = 1
		left = reachZeroHelper(arr, start - arr[start], visited)
		right = reachZeroHelper(arr, start + arr[start], visited)
		return (left or right)

Walkthrough

With Input: [3, 2, 4, 5, 0, 1, 2, 9, 3] and starting index: 0:

Since the starting vertex is 0,left = reachZeroHelper(arr, 0 - 3, visited) and right = reachZeroHelper(arr, 0 + 3, visited).
Therefore left = false, since $-3 < 0$ .
After its recursive call, right = reachZeroHelper(arr, 3 - 5, visited) || reachZeroHelper(arr, 3 + 5, visited).
reachZeroHelper(arr, 3 - 5, visited) = false, since $-2 < 0$ , soright = reachZeroHelper(arr, 8, visited)
After another recursive call,right = reachZeroHelper(arr, 8 - 3, visited) || reachZeroHelper(arr, 8 + 3, visited).
reachZeroHelper(arr, 8 + 3, visited) = false, since 11 > 9 - 1, soright = reachZeroHelper(arr, 8 - 3, visited).
After another recursive call, right = reachZeroHelper(arr, 5 - 1, visited) || reachZeroHelper(arr, 5 + 1, visited).
Since arr[4] == 0, we return true.

Runtime Analysis

Since we only need to check each index at most once, the algorithm runs in $O(N)$ time. If your algorithm has a runtime any greater than linear, then you are re-checking indices and can get into an infinite loop.