[Java/C++] Clean Code - No Cache


  • 7

    Java

    class Solution {
        public int longestLine(int[][] M) {
            if (M.length == 0 || M[0].length == 0) return 0;
            int m = M.length, n = M[0].length;
            int max = 0, hori = 0, vert = 0, inc = 0, desc = 0;
            for (int i = 0; i < m; i++, hori = 0) {
                for (int j = 0; j < n; j++) {
                    hori = M[i][j] > 0 ? hori + 1 : 0;
                    max = Math.max(max, hori);
                }
            }
            for (int j = 0; j < n; j++, vert = 0) {
                for (int i = 0; i < m; i++) {
                    vert = M[i][j] > 0 ? vert + 1 : 0;
                    max = Math.max(max, vert);
                }
            }
            for (int k = 0; k < m + n; k++, inc = 0, desc = 0) {
                // increasing start from left cells then bottom cells
                for (int i = Math.min(k, m - 1), j = Math.max(0, k - m); i >= 0 && j < n; i--, j++) {
                    inc = M[i][j] > 0 ? inc + 1 : 0;
                    max = Math.max(max, inc);
                }
                // decreasing start from left cells then top cells;
                for (int i = Math.max(m - 1 - k, 0), j = Math.max(0, k - m); i < m && j < n; i++, j++) {
                    desc = M[i][j] > 0 ? desc + 1 : 0;
                    max = Math.max(max, desc);
                }
            }
            return max;        
        }
    }
    

    c++

    class Solution {
    public:
        int longestLine(vector<vector<int>>& M) {
            if (M.empty() || M[0].empty()) return 0;
            int m = M.size(), n = M[0].size();
            int maxl = 0, hori = 0, vert = 0, inc = 0, desc = 0;
            for (int i = 0; i < m; i++)
                for (int j = 0, hori = 0; j < n; j++, maxl = max(maxl, hori))
                    hori = M[i][j] ? hori + 1 : 0;
    
            for (int j = 0; j < n; j++)
                for (int i = 0, vert = 0; i < m; i++, maxl = max(maxl, vert))
                    vert = M[i][j] ? vert + 1 : 0;
    
            for (int k = 0; k < m + n; k++) {
                for (int i = min(k, m - 1), j = max(0, k - m), inc = 0; i >= 0 && j < n; i--, j++, maxl = max(maxl, inc))
                    inc = M[i][j] ? inc + 1 : 0;
                for (int i = max(m - 1 - k, 0), j = max(0, k - m), desc = 0; i < m && j < n; i++, j++, maxl = max(maxl, desc))
                    desc = M[i][j] ? desc + 1 : 0;
            }
            return maxl;
        }
    };
    

  • 0
    Z

    Good code! Same performance as DP with O(1) space. DP is not necessary.


  • 0
    A

    Beat 95% of the other solutions.
    Similar idea, but only iterate the grid once. The basic idea is simple, take horizontal for example: when we see 1, if the left number is 0 then count the consecutive ones from this position on, and the update max. The second 1 from 1-1 sequence will be skipped. so the time complexity would be O(mn).

    public int longestLine(int[][] M) {
            if (M.length == 0 || M[0].length == 0) return 0;
            int r = M.length, c = M[0].length, max = 0;
            for (int i = 0; i < r; i ++) {
                for (int j = 0; j < c; j++) {
                    int curRow = 0, curCol = 0, diag = 0, anti = 0;
                    if (M[i][j] == 1) {
                        if (j == 0 || M[i][j-1] == 0) {
                            int col = j;
                            while (col < c && M[i][col] == 1) {
                                curRow++;
                                col++;
                            }
                            max = Math.max(max, curRow);
                        }
                        if (i == 0 || M[i-1][j] == 0) {
                            int row = i;
                            while (row<r && M[row][j] == 1) {
                                curCol++;
                                row++;
                            }
                            max = Math.max(max, curCol);
                        }
    
                        if (i == 0 || j == 0 || M[i-1][j-1] == 0) {
                            int row = i, col = j;
                            while (row <r && col < c && M[row][col] == 1) {
                                diag++;
                                row++; col++;
                            }
                            max = Math.max(max, diag);
                        }
    
                        if (i == 0 || j == c-1 || M[i-1][j+1] == 0) {
                            int row = i, col = j;
                            while (row <r && col >=0 && M[row][col] == 1) {
                                anti++;
                                row++; col--;
                            }
                            max = Math.max(max, anti);
                        }
                    }
                }
            }
            return max;
        }
    

Log in to reply
 

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