Java Solution using only ONE 2-D array for DP


  • 0
    F
    public class Solution {
        public int longestLine(int[][] mtx) {
            if (mtx==null || mtx.length==0 || mtx[0].length==0) {
                return 0;
            } else {
                int[][] dp = new int[mtx[0].length][4];
                int max = 0;
                
                for (int r = 0; r < mtx.length; r++) {
                    int preDiagLen = 0;
                    for (int c = 0; c < mtx[r].length; c++) {
                        if (mtx[r][c] == 0) {
                            preDiagLen = dp[c][2];
                            dp[c][0] = dp[c][1] = dp[c][2] = dp[c][3] = 0;
                        } else {
                            int tmp = dp[c][2];
                            dp[c][0] = c>0?dp[c-1][0]+1:1;
                            dp[c][1] = dp[c][1]+1;
                            dp[c][2] = preDiagLen+1;
                            dp[c][3] = c<mtx[r].length-1?dp[c+1][3]+1:1;
                            preDiagLen = tmp;
                            max = Math.max(max, Math.max(dp[c][0], dp[c][1]));
                            max = Math.max(max, Math.max(dp[c][2], dp[c][3]));
                        }
                    }
                }
                
                return max;
            }
        }
    }
    

Log in to reply
 

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