Fast Python solution using NumPy


  • 5

    Fastest posted Python solution so far. Takes about 120 ms, of which about 80 ms are for judge overhead and importing NumPy. The other three Python solutions posted so far take about 350-850 ms, of which about 40 ms are for judge overhead.

    My two-dimensional paths array tells the number of paths ending at each cell with the moves made so far. So initially all zeros except for the starting position, which has one path (the empty path). The for each move, I spread each path number in all four directions.

    This only keeps track of the paths staying inside the boundary. To compute how many paths went outside in the latest move, I take all previous paths, multiply them by 4 (for the four directions) and subtract the new number of inside-paths after the move.

    import numpy as np
    
    class Solution(object):
        def findPaths(self, m, n, N, i, j):
            paths = np.zeros((m, n), dtype=np.int64)
            paths[i][j] = 1
            out = 0
            mod = 10**9 + 7
            for _ in range(N):
                prev = paths % mod
                paths = prev - prev
                paths[1:] += prev[:-1]
                paths[:-1] += prev[1:]
                paths[:,1:] += prev[:,:-1]
                paths[:,:-1] += prev[:,1:]
                out += 4 * prev.sum() - paths.sum()
            return int(out % mod)
    

    A slightly shorter version using Python ints (which can grow arbitrarily large) and doing mod 109-7 only at the end:

    import numpy as np
    
    class Solution(object):
        def findPaths(self, m, n, N, i, j):
            paths = np.zeros((m, n), dtype=object)
            paths[i][j] = 1
            out = 0
            for _ in range(N):
                prev = paths
                paths = prev * 0
                paths[1:] += prev[:-1]
                paths[:-1] += prev[1:]
                paths[:,1:] += prev[:,:-1]
                paths[:,:-1] += prev[:,1:]
                out += 4 * prev.sum() - paths.sum()
            return out % (10**9 + 7)
    

    Still fairly fast, about 190 ms.


Log in to reply
 

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