Problem statement

https://leetcode.com/problems/out-of-boundary-paths/

Solution

Let dp(N, i, j) be number of solutions if we start from point (i, j) and we an make at most N steps. Then we need to consider the cases:

  1. If i == m or j == n or i < 0 or j < 0, it means that we reached boundary, so we return 1: we found one more path.
  2. If N == 0, it means, that we out of moves, and we did not reached boundary yet, so we return 0.
  3. Finally, we try to make 4 steps to all directions and return sum of all number of options. Note, that we visit this 3-rd line only if N >= 1, so when we call function with first argument N-1, number of moves never be negative.

Complexity

We have O(m*n*N) states with 4 moves from each state, so we have time and space complexity O(m*n*N).

Code

class Solution:
    def findPaths(self, m, n, N, i, j):
        M = 10**9+7
        @lru_cache(None)
        def dfs(N, i, j):
            if i == m or j == n or i < 0 or j < 0: return 1
            if N == 0: return 0
            return sum(dfs(N-1,i+x,j+y) for x,y in [[-1,0],[1,0],[0,-1],[0,1]])%M
        
        return dfs(N,i,j)

Solution 2

This solution is inspired by this idea https://leetcode.com/problems/out-of-boundary-paths/discuss/341414/Possibility-of-O(m3n3logN)-solution. The idea is to reformulate problem as graph traversal problem, where we need to find number of paths. We have mn states in our grid and we create (m+2)*(n+2) x (m+2)*(n+2) adjacency matrix, where we add empty border.

Complexity

It is O(n^3*m^3*log(N)), because we need to evaluate power of matrix. Unfortunatelly it will give TLE in this problem, however I think it can be interesting to investigate this approach.

Code

import numpy as np

class Solution:
    def findPaths(self, m, n, N, a, b):
        def power(M, n, MOD):
            result = np.eye(len(M), dtype = int)
            while n > 0:
                if n%2: result = np.dot(M, result) % MOD
                M = np.dot(M, M) % MOD
                n //= 2
            return result

        M, MOD = np.zeros(((m+2)*(n+2), (m+2)*(n+2)), dtype = int), 10**9+7
        neibs = [[0,1],[0,-1],[1,0],[-1,0]]

        for i in range(0, m+2):
            for j in range(0, n+2):
                if i == 0 or i == m+1 or j == 0 or j == n+1:
                    M[i*(n+2)+j][i*(n+2)+j] = 1
                else:
                    for dx, dy in neibs:
                        M[i*(n+2)+j][(i+dx)*(n+2)+(j+dy)] = 1

        S = power(M, N, MOD)
        T = S[(a+1)*(n+2)+b+1]
        return int(T.sum() - T.reshape(m+2, n+2)[1:m+1,1:n+1].sum()) % MOD