# Question @ Paypal: Can Mario complete the Level?

• 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 `level`.

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[0] = level[0] != -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[1] - array[0] <=2 and array[1] != -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]:
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:
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`````````

• Using DP we can find out.

Check my solution in javascript. It is basically using the logic to get all possible combination and verifying if there is a successful jump. If there is a successful jump. A `true` output would be displayed.

``````let arr = [1,2,3,4,3,1,4,0];

function canComplete(arr, index){
if(index == arr.length - 1 ){
return true;
}
let success = false;
if(Math.abs(arr[index] - arr[index+1]) <= 2){
success = canComplete(arr, index + 1);
}
if(!success && Math.abs(arr[index] - arr[index+2]) <= 2){
success =  canComplete(arr, index + 2);
}
return success;

}

console.log(canComplete(arr,0));
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.