Leetcode Longest Increasing Path in a Matrix problem solution

YASH PAL,

In this Leetcode Longest Increasing Path in a Matrix problem solution You are given an m x n integers matrix, return the length of the longest increasing path in the matrix. From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Leetcode Longest Increasing Path in a Matrix problem solution

Problem solution in Python.

def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        memo={}
        def helper(pos):
            if pos in memo:
                return memo[pos]
            i=pos[0]
            j=pos[1]
            ans=1
            for k1,k2 in [[0,1],[0,-1],[1,0],[-1,0]]:
                if 0<=i+k1<len(matrix) and 0<=j+k2<len(matrix[0]) and matrix[i][j]>matrix[i+k1][j+k2]:
                    ans=max(ans,1+helper((i+k1,j+k2)))
            memo[pos]=ans
            return ans
        ans=0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if (i,j) not in memo:
                    ans=max(ans,helper((i,j)))
        return ans

Problem solution in Java.

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length==0) return 0;
        Integer[][] max = new Integer[matrix.length][matrix[0].length];
        int maxmax = 0;
        for(int i = 0; i<matrix.length; i++){
            for(int j = 0; j<matrix[0].length; j++){
                dfs(matrix, max, i, j);
                maxmax = Math.max(maxmax, max[i][j]);
            }
        }
        return maxmax;
    }
    public int dfs(int[][] matrix, Integer[][] max, int y, int x){
        if(max[y][x]==null){
            int max_dist = 0;
            int target = matrix[y][x];
            if(y-1>=0 && matrix[y-1][x]>target){
                dfs(matrix, max, y-1, x);
                max_dist = Math.max(max_dist, max[y-1][x]);
            }
            if(y+1<matrix.length && matrix[y+1][x]>target){
                dfs(matrix, max, y+1, x);
                max_dist = Math.max(max_dist, max[y+1][x]);
            }
            if(x-1>=0 && matrix[y][x-1]>target){
                dfs(matrix, max, y, x-1);
                max_dist = Math.max(max_dist, max[y][x-1]);
            }
            if(x+1<matrix[0].length && matrix[y][x+1]>target){
                dfs(matrix, max, y, x+1);
                max_dist = Math.max(max_dist, max[y][x+1]);
            }
            max[y][x] = max_dist+1;
        }
        return max[y][x];
    }
}

Problem solution in C++.

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if(m==0) return 0;
        int n = matrix[0].size();
        int max_len = -1;
        vector<vector<int>> dp(m,vector<int>(n,-1));
        for(int i = 0;i<m;i++)
            for(int j = 0;j<n;j++)
                max_len = max(max_len,dfs(i,j,matrix,dp));

        return max_len;  
    }
    int dfs(int i,int j,vector<vector<int>>& matrix, vector<vector<int>>&dp)
    {
        if(dp[i][j]!=-1) return dp[i][j];
        vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,1},{0,-1}};
        int m = matrix.size();
        int n = matrix[0].size();
        int length = 1;
        for(auto dir:dirs)
        {
            int nextI = i+dir.first;
            int nextJ = j+dir.second;
            if(nextI<0 || nextI>=m || nextJ<0 || nextJ>=n) continue;
            if(matrix[nextI][nextJ] > matrix[i][j])
                length = max(length,1+dfs(nextI,nextJ,matrix,dp));
        }
        dp[i][j] = length;
        return dp[i][j];
        
    }
};

Problem solution in C.

#define MAXN 2048
#define zip(x,y) ((x)*(col)+(y))

int max(int a, int b)
{
    return a > b?a:b;
}
int dp[MAXN*MAXN];
int dfs(int x,int y,const int row,const int col,int last,int **mat)
{
     if(x >= row || y >= col || x < 0 || y < 0 || mat[x][y] <= last)
        return 0;
    int t = zip(x,y);
    if(dp[t]) 
        return dp[t];
    int ret = dfs(x-1,y,row,col,mat[x][y],mat);
    ret = max(ret,dfs(x+1,y,row,col,mat[x][y],mat));
    ret = max(ret,dfs(x,y-1,row,col,mat[x][y],mat));
    ret = max(ret,dfs(x,y+1,row,col,mat[x][y],mat));
    return dp[t] = ++ret;
 }

 int longestIncreasingPath(int** mat, int row, int col) {
     int ret = 0;
     memset(dp,0,sizeof(int)*zip(row,col));
     for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++)
            ret = max(ret,dfs(i,j,row,col,mat[i][j] - 1,mat));
    return ret;
 }

coding problems