Skip to content

Instantly share code, notes, and snippets.

@datlife datlife/move_forward.py
Last active Nov 1, 2018

Embed
What would you like to do?
"""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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.