562. Longest Line of Consecutive

Description

Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.

Example:

Input:
[[0,1,1,0],
[0,1,1,0],
[0,0,0,1]]
Output: 3

Hint: The number of elements in the given matrix will not exceed 10,000.

Solution

Brute-force using iteration, O(mn * ?), S(1)

class Solution {
    public int longestLine(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        
        for (int[] row : matrix) {
            int len = 0;
            
            for (int j = 0; j < n; ++j) {
                if (row[j] == 0) {
                    len = 0;
                } else {
                    max = Math.max(++len, max);
                }
            }
        }
        
        for (int j = 0; j < n; ++j) {
            int len = 0;
            
            for (int i = 0; i < m; ++i) {
                if (matrix[i][j] == 0) {
                    len = 0;
                } else {
                    max = Math.max(++len, max);
                }
            }
        }
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int len = 0;
                
                for (int k = 0; i + k < m && j + k < n; ++k) {
                    if (matrix[i + k][j + k] == 0) {
                        len = 0;
                    } else {
                        max = Math.max(++len, max);
                    }
                }
            }
        }
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int len = 0;
                
                for (int k = 0; i + k < m && j - k >= 0; ++k) {
                    if (matrix[i + k][j - k] == 0) {
                        len = 0;
                    } else {
                        max = Math.max(++len, max);
                    }
                }
            }
        }
        
        return max;
    }
}

其中枚举diagonal和anti-diagonal是可以优化的，分别枚举第一行和最后一行就行了。这样可以将时间复杂度降到O(mn)。

3D-DP, O(mn), S(mn)

class Solution {
    public int longestLine(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        int[][][] dp = new int[m + 1][n + 2][4]; // for conveniency
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    continue;
                }
                dp[i + 1][j + 1][0] = 1 + dp[i + 1][j][0];
                dp[i + 1][j + 1][1] = 1 + dp[i][j + 1][1];
                dp[i + 1][j + 1][2] = 1 + dp[i][j][2];
                dp[i + 1][j + 1][3] = 1 + dp[i][j + 2][3];
                max = Math.max(max(dp[i + 1][j + 1]), max);
            }
        }
        
        return max;
    }
    
    private int max(int[] a) {
        int max = Integer.MIN_VALUE;
        for (int v : a) {
            max = Math.max(v, max);
        }
        return max;
    }
}

2D-DP, O(mn), S(n)

class Solution {
    public int longestLine(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[n + 2][4]; // for conveniency
        
        for (int i = 0; i < m; ++i) {
            int prev = 0;
            
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    prev = dp[j + 1][2];    // don't forget to update prev!
                    Arrays.fill(dp[j + 1], 0);
                } else {
                    int tmp = dp[j + 1][2];
                    
                    dp[j + 1][0] = 1 + dp[j][0];
                    dp[j + 1][1] += 1;
                    dp[j + 1][2] = 1 + prev;
                    dp[j + 1][3] = 1 + dp[j + 2][3];
                    max = Math.max(max(dp[j + 1]), max);
                    
                    prev = tmp;
                }
            }
        }
        
        return max;
    }
    
    private int max(int[] a) {
        int max = Integer.MIN_VALUE;
        for (int v : a) {
            max = Math.max(v, max);
        }
        return max;
    }
}