Memory Limit Exceeded for Jump Game


  • 0
    S

    I test it on my local and seems works fine.

    class Solution:
        # @param A, a list of integers
        # @return a boolean
        def canJump(self, A):
            pos = 0
            if A[0] == 0 and len(A) != 1:
                return False
            if A[pos] >= len(A) - 1:
                return True
            return any(self.canJump(A[x:]) for x in range(1,A[pos]))

  • 0
    S

    AFAIK, python pass reference by default. But in this case of A[x:], they will do a deep copy, which means it will consume a pile of memory in the entire recursion.

    I did some change like below. At least, it isn't MLE any more.

    class Solution:
        # @param A, a list of integers
        # @return a boolean
    
    
        def canJumpIntern(self, A, pos):
            if A[pos] >= len(A) - 1:
                return True
        
            return any(self.canJumpIntern(A, x) for x in range(1,A[pos]))
            
        def canJump(self, A):
            pos = 0
            if A[0] == 0 and len(A) != 1:
                return False
            return self.canJumpIntern(A, 0)
    

    Maybe I am wrong, I don't quite understand what exactly the strategy in your code. For example, A[pos] stands for length. So, x is also a length. How to understand it becomes a index A[x:] though?

    I suggest to elaborate the idea.


  • 0
    S

    Hello Shangrilla, thank you for the respond.

    My strategy is using recursive. So if we can reach A[pos], then the function result depends on the result of the rest array A[pos:].

    A[pos] is a length, you're right, and it is the maximum steps we can go. So I'm iterate on all possible steps to see if there's a way to reach the end.

    Not sure I explained it clear, let me know if you have any question.


  • 0
    S

    By the way your solution didn't work for me, the test case [2,3,0,1,4] will get into infinite loop and fail with "maximum recursion depth exceeded" error.


  • 0
    S

    I hit a dead end by keeping your recursive idea. In essence, I don't think it can be solved by this way. I suggest to find a good approach from this post


Log in to reply
 

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