Question @ Paypal: Can Mario complete the Level?

  • 0

    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?

  • 0

    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
               reachable[i+1] |= reachable[i] and level[i+1] - level[i] <= 2
               reachable[i+2] |= reachable[i] and (level[i] > level[i+1]) and (level[i] >= level[i+2])
       return reachable[-1]

  • 0

    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	
    			return False
      		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
    				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
        			return False
        	return True```

  • 0

    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;

Log in to reply

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