less than 1 minute read

Advancing through array - Elements of Programming Interviews (EPI)

Problem:

Write a function to determine if end of array is reachable. Each element in the array denotes the maximum forward steps that are allowed. Example: [1,4,3,2,1] should return True since we can easily reach the end of the array. [3,1,0,0,1,0,4,5]] should return False since we cannot reach the end of the array.

Solution:

We tried to write a recursive function for this but it failed for some unseen test cases. Instead we considered the farthest index of A we can reach from each index starting from 0. If at any point we reach the situation where the current index i is greater than the farthest index of A that we have been able to reach so far then we cannot reach the end of the array.

def can_reach_end(A: List[int]) -> bool:
    farthest, i = 0, 0
    end = len(A) - 1
    while i <= farthest and i < end:
        farthest = max(farthest, i + A[i])
        i += 1
        if farthest >= end:  # In case end is reachable sooner
            break
    return farthest >= end