Java easy-to-understand O(m*n) solution

  • 0

    If using the model of DP to treat this problem, your sub-problem is (for each cell): which line
    ( | , __ , \ , / ) gives the MAX (the direction of arrow totally depends on how you traverse your matrix). Treat each row as if this is the last row of your matrix, and use a 3d array ( int[m][n][4] ) to memoize the result. I saw @compton_scatter has similar idea, but I figured this out myself, and mine is probably little bit cleaner.
    The memoized results of the example is shown below:

    int[][] directions = new int[][]{{-1,-1},{-1,0},{0,-1},{-1,1}};

    My code:

        public int longestLine(int[][] M) {
            int[][] directions = new int[][]{{-1,-1},{-1,0},{0,-1},{-1,1}};
            if(M.length==0)return 0;
            int[][][] memo = new int[M.length][M[0].length][4];
            int res = 0;
            for(int i=0;i<M.length;i++){
                for(int j=0;j<M[0].length;j++){
                        for(int k=0;k<4;k++){
                            int r = i+directions[k][0], c = j+directions[k][1];
                            memo[i][j][k] = 1;
                                memo[i][j][k] += memo[r][c][k];
                                res = Math.max(res, memo[i][j][k]);
                            res = Math.max(res, memo[i][j][k]);
            return res;

Log in to reply

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