A couple of Python solutions, not sure about complexity


  • 1

    The (almost) obvious DP solution:

        can_jump = [set() for __ in xrange(len(stones))]
        can_jump[0] = {0}
        farthest = 1
        for i in xrange(1, len(stones)):
            if stones[i] > farthest:
                return False
            m = 0
            for j in xrange(i):
                d = stones[i] - stones[j]
                if d in can_jump[j] or d - 1 in can_jump[j] or d + 1 in can_jump[j]:
                    can_jump[i].add(d)
                    m = max(m, d + 1)
            farthest = max(farthest, stones[i] + m)
        return bool(can_jump[-1])
    

    That's O(n^2), but without the farthest check it TLEs on a very long input, even though it seems like the “size <= 1100” part is telling us any O(n^2) solution is OK. Indeed, it only takes less than 200 ms to solve that input, but it still TLEs. Cost me 10 minutes of penalty time. The total run time after submission is 1800 ms (slow!).

    A more efficient solution can be achieved by reducing the inner loop to only those stones that are possible starting points for a jump to the current stone. To do that, we need to compute all possible destinations when we're processing a stone. Here is the code:

        stones_set = set(stones)
        incoming_jumps = defaultdict(set)
        incoming_jumps[1] = {1}
        for stone in stones[1:]:
            for jump in incoming_jumps[stone]:
                for d in xrange(-1 if jump > 1 else 0, +2):
                    if stone + jump + d in stones_set:
                        incoming_jumps[stone + jump + d].add(jump + d)
        return bool(incoming_jumps[stones[-1]])
    

    The complexity of this solution is tricky to figure out. It feels like O(n^2) because of two loops (never mind the third one, it's only 2-3 iterations). But the inner loop is over possible incoming jumps, and it doesn't get as large as O(n). Even if there is a lot of stones, it looks like the inner loops only grows as O(sqrt(n)) because the number of incoming jumps increases only when we have yet another longer jump, but longer jumps require a lot of previous jumps to “charge”, see:

    1 - can be reached in one way only
    2 - ditto (1 -> 2)
    3 - 2 ways (2 -> 3 or 0 -> 1 -> 3)
    4 - 2 ways (3 -> 4 or 1 -> 2 -> 4)
    5 - 2 ways (4 -> 5 or 2 -> 3 -> 5)
    6 - 3 ways (5 -> 6, 3 -> 4 -> 6, 1 -> 3 -> 6)
    7 - 3 ways (6 -> 7, 4 -> 5 -> 7, 2 -> 4 -> 7)
    8 - 3 ways (7 -> 8, 5 -> 6 -> 8, 3 -> 5 -> 8)
    9 - 3 ways (8 -> 9, 6 -> 7 -> 9, 4 -> 6 -> 9)
    10 - 4 ways (9 -> 10, 7 -> 8 -> 10, 5 -> 7 -> 10, 1 -> 3 -> 6 -> 10)

    And so on. So it looks like the complexity is actually O(n^1.5). The total runtime is 300 ms. Much better than the first variant!


  • 0
    A

    @SergeyTachenov can check my solution - cost about 50 - 89ms in python. very straightforward dp top-down with memoization


Log in to reply
 

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