5 lines O(N) Python with explanation

  • 6

    Check comments in the code.

    def jump2(self, A):
        Basically it's a shortest-path problem. 
        As an unweighted graph, BFS should be able to solve it in O(|E|).
        But as it's an array with non-negative numbers, we can't jump backward. 
        So we can do better here.
        Suppose we devided the arrays into segments depending on the elment 
        in the array. So for each segment, we find the farthest index we can 
        jump. For example, the first segment is always A[0]. The second will be
        from A[1] to A[A[0]]. The third will be from A[A[0]] to the farthest 
        index we can find in the second segment. We start looking between 
        the end of the last segment and the begin of the next segment.
        ans = lastIdx = nextIdx = 0
        while nextIdx < len(A) - 1:
            ans += 1
            lastIdx, nextIdx = nextIdx, max(i + A[i] for i in xrange(lastIdx, nextIdx + 1))
        return ans

  • 0
    def jump(nums):
        return 1 if len(nums) - 1 <= nums[0] else 1 + self.jump(nums[max([(i + nums[i], i) for i in xrange(nums[0] + 1)])[1]:])

    Think you for your code! Here is my question: I think the thought is similar to yours, but mine got an MLE. Is it recursion's fault?

  • 0

    There's a stack limit in Python, which is by default 256 and has been hit pretty hard by your code.

    Check this case: [1] * 100000

  • 0

    Yes, I got an MLE just because of it. Is the stack limit the limit of recursion? Could you give me some suggestions that I improve it? Thank you!

  • 0

    yep. your recursion is too deep. I suggest using iteration instead of recursion to get rid of the limit.

  • 0

    Thank you! And BTW, your code is great!

  • 0

    better if you let

    lastIdx = nextIdx + 1

    in each iteration

Log in to reply

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