Magic on leetcode
Jon Snow
144
Aug 11, 2020
Aug 11, 2020

Question - 576. Out of Boundary Paths

I wrote the solution for this question and got TLE for 89th test case out of 94 and when I ran a similar looking solution from Discussion, it got accepted!! How is this possible??

My solution ( TLE on 89th testcase out of 94)

long long int M = 1000000007,dp[55][55][55] = {0};
    vector<vector<int>> dir{{1,0},{-1,0},{0,1},{0,-1}};
	
    int findPaths(int m, int n, int N, int i, int j) {
        if(dp[i][j][N]!=0) return dp[i][j][N];
        if(N==0) return dp[i][j][N] = 0;
        if(i==0) dp[i][j][N] = (dp[i][j][N]+1)%M;
        if(i==m-1) dp[i][j][N] = (dp[i][j][N]+1)%M;
        if(j==0) dp[i][j][N] = (dp[i][j][N]+1)%M;
        if(j==n-1) dp[i][j][N] = (dp[i][j][N]+1)%M;
        for(int k=0;k<4;k++)
        {
            int x=i+dir[k][0],y=j+dir[k][1];
            if(x>=0 and x<m and y>=0 and y<n) dp[i][j][N] = (dp[i][j][N]+findPaths(m,n,N-1,x,y))%M;
        }
        return dp[i][j][N];
    }

Similar Solution which Got AC

long long int mem[55][55][55];
    long long int findP(int m, int n, int N, int i, int j){
         int mod=1e9+7;
        if(i<0 or j<0 or i>=m or j>=n) return 1;
        if(N<=0) return 0;
        if(mem[i][j][N]!=-1) return mem[i][j][N];
        pair<int,int> p[]={{1,0},{0,1},{-1,0},{0,-1}};
        int h=0;
        for(int k=0;k<4;k++){
            int x=p[k].first+i;
            int y=p[k].second+j;
            h+=findP(m,n,N-1,x,y);
            h=h%mod;
        }
        return mem[i][j][N]=h;
    }
    int findPaths(int m, int n, int N, int i, int j) {
        int mod=1e9+7;
        memset(mem,-1,sizeof(mem));
        long long int p=findP(m,n,N,i,j);
        return p%mod;;
    }

Can anyone tell me if there is something wrong in my solution or its magic?

Comments (1)