move_forward.py

"""Move Forward
Start from the first element in the array (A), index is i. Move forward by A[i] steps max.  
The algorithm is to return true/false, to indicate whether we can move from the first element
to the last element in the array
A = [2, 0, 1, 2, 0, 3] --> True

# Assumption:
-------------
    * A[i] > 0 and there are [1 ... N] possible steps A[i] can move if A[i] = N.

# Solution Discussion:
----------------------
    * I approach this problem by keeping track of a cursor while iterating through
     all the elements. For every iteration, this cursor can be updated if potential steps
     is greater than current cursor.
     
    * Initially, I thought checking A[i] steps is enough. However, it turns out this is
    harder than expeceted because of possible steps A[i] can move in one iteration.

# Complexity Analysis:
----------------------
    * Time: O(N) Space: O(1)

# Run test:
-----------
>> pytest .

"""
import collections


def move_forward(A):
    """Indicate if we can move from 1st element to
    last element in an array. That is, at index i, 
    can can move A[i] steps max.
    
    Args:
        A - an array of integers

    Return: 
        True if we can move forward in A
    """
    if not A: return False
    if A[0] == 0 and len(A) > 2: return False

    curr_pos = 0
    for idx, steps in enumerate(A):
        if idx > curr_pos:
            return False
        curr_pos = max(steps + idx, curr_pos)
    return True


def test_move_forward():
    test = collections.namedtuple('TestCase', ['input', 'expected'])
    cases = [
        test([2, 0, 1, 2, 0 ,3], True),
        test([0], True),
        test([0, 1], False),
        test([1, 0, 4], False),
        test([1, 1, 0], True),
        test([1, 0, 1], False),
    ]
    for t in cases:
        assert move_forward(t.input) == t.expected