The problem is as follows: Given an array, which represents the levels in Mario Game, determine whether mario can complete the level or not. Mario can only take 1 jump and the jump can be of maximum height 2. He can also jump directly by avoiding pits. He can jump down from any height.
For example, array is [0,1,-1,1,2,3,0]: So, Mario starts from 0th level, jumps to 1, further jumps to 1 again by avoiding pit (represented by -1), Jumps to 2 (it is allowed since he can jump maximum height 2 levels from current height), jumps to 3 and jumps down to 0 and thus clears the level.
However, if array is: [0,3,0]: Then mario cannot complete the level (return False) If array is: [1,-1,1]: Mario can complete the level by directly jumping to 1 and avoiding the pit.
One more important case is: [1,2,3,4,1,4,0]: Mario should jump from 1 to 2 to 3 to 4. But from here, he should not jump down to 1 as he cannot climb back up to 4. Instead he should directly jump from 4 to 4 and then jump down to 0.
How can you solve this efficiently?
Not sure if this is the most efficient solution, but this runs with O(n) complexity as it iterates through the given array once.
The idea here is create another array,
reachable, that is of equal length to the
level array. The ith index in
reachable represents whether or not Mario can reach the ith square in
Starting from the first square and working our way to the last, test to see if Mario can jump from the current square to the next or jump over the next to the one following that. After doing this for each square in the level,
reachable[i] show if Mario can reach the ith square in level.
def mario(level): reachable = [False for i in range(len(level))] reachable = level != -1 for i in range(len(level)): if(level[i] == -1): reachable[i] = False if(i+1<len(level)): reachable[i+1] |= reachable[i] and level[i+1] - level[i] <= 2 if(i+2<len(level)): reachable[i+2] |= reachable[i] and (level[i] > level[i+1]) and (level[i] >= level[i+2]) return reachable[-1]
Good one. However, I think your solution might fail for this test case
[0,2,4,0,3,1]. It should be False, your code will return True. Mario can't jump from 4 to 3. He can only jump at the same level. So, from 4 he'll go down to 0, but now can't climb up!
My idea was to use 3 pointers to keep track! But it's not efficient and full-proof!
if len(array) == 0: return True if len(array) == 1: return True if len(array) == 2: if array - array <=2 and array != -1: return True else: return False else: ptr1 = 0 ptr2 = 1 ptr3 = 2 i = 0 while i < len(array) - 2: if array[ptr3] == array[ptr1] and array[ptr2] < array[ptr1]: #Simply jump to ptr3 i = ptr3 ptr1 = ptr3 ptr2 = ptr1 + 1 ptr3 = ptr2 + 1 elif array[ptr2] == -1: #Can't ccomplete the level return False elif array[ptr2] - array[ptr1] <= 2: #Jump to ptr2: i = ptr2 ptr1 = ptr2 ptr2 = ptr1 + 1 ptr3 = ptr2 + 1 else: return False #Before returning, make sure you've traversed the whole array if ptr3 > len(array) - 1 and ptr1 <= len(array)-1 and ptr2 <= len(array)-1: if array[ptr2] - array[ptr1] <= 2: return True else: return False return True```