O(mn) time no extra space solution


  • 1
    L

    Four directions, which represents horizontal, vertical, diagonal, anti-diagonal.

    basic idea is to only count a line if it is a start point. A start point could either be in the boundary or previous node in the direction is a zero.

    public class Solution {
        private static int[][] dirs = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
        private boolean isBoundary(int type, int i, int j, int maxRight) {
            if ((type == 0 && (j == 0)) ||
                (type == 1 && (i == 0)) ||
                (type == 2 && (i == 0 || j == 0)) ||
                (type == 3 && (i == 0 || j == maxRight))) {
                    return true;
            } else {
                return false;
            }
        }
        public int longestLine(int[][] M) {
            int maxVal = 0;
            for (int i=0; i<M.length;i++) {
                for (int j= 0; j<M[i].length;j++) {
                    for (int k= 0; k<4; k++)
                    if (M[i][j] == 1 && (isBoundary(k, i, j, M[i].length - 1) || M[i - dirs[k][0]][j - dirs[k][1]] == 0)) {
                        int tmpVal = 0;
                        int ii = i, jj = j;
                        while (ii >= 0 && ii < M.length && jj >=0 && jj < M[i].length && M[ii][jj] == 1) {
                            ii += dirs[k][0];
                            jj += dirs[k][1];
                            tmpVal++;
                        }
                        maxVal = tmpVal > maxVal ? tmpVal : maxVal;
                    }
                }
            }
            return maxVal;
        }
    }
    

  • 1

    Do you really think it is O(mn). What will be complexity when matrix contains all ones?


  • 0
    L

    @vinod23 yes it is. Because of this line:

    isBoundary(k, i, j, M[i].length - 1) || M[i - dirs[k][0]][j - dirs[k][1]] == 0)

    It means either it is a boundary position, or previous position in direction "k" is 0. Such check runs in o(1) time. In the case matrix I'd all ones, this condition will only be true for boundary positions.


  • 0

    @laosunhust And what about the while loop which you have used? how much iterations it will take in worst case?


  • 0
    L

    @vinod23 the while loop will be executed only once for each consecutive ones in horizontal / vertical / diagonal / anti-diagonal direction. There won't be revisits for each one in each direction.


  • 1

    I've used this idea in two other problems and it's fascinating how much trouble some have understanding it :-P

    In this problem I don't think it's that advantageous, though. Here's a small maybe more "normal" variation that's also O(mn) time and O(1) space, analyzing entire rows/columns/etc.

                if (isBoundary(k, i, j, M[i].length - 1)) {
                    int tmpVal = 0;
                    int ii = i, jj = j;
                    while (ii >= 0 && ii < M.length && jj >=0 && jj < M[i].length) {
                        tmpVal = (tmpVal + 1) * M[ii][jj];
                        maxVal = tmpVal > maxVal ? tmpVal : maxVal;
                        ii += dirs[k][0];
                        jj += dirs[k][1];
                    }
                }

  • 0
    M

    Efficient and easy understanding approach, thanks. My re-writing:

    int[][] dirs = {{1, 0}, {0, 1}, {1, 1}, {-1, 1}};
    
        private boolean isStartingPoint(int r, int c, int dir, int[][] M){
            return r - dirs[dir][0] < 0 || c - dirs[dir][1] < 0 || r - dirs[dir][0] >= M.length || M[r - dirs[dir][0]][c - dirs[dir][1]] == 0;
        }
    
        public int longestLine(int[][] M) {
            if (M.length == 0 || M[0].length == 0) return 0;
            int res = 0, R = M.length, C = M[0].length;
            
            for(int r = 0; r < R; r++){
                for(int c = 0; c < C; c++){
                    if(M[r][c] == 1){
                        for(int dir = 0; dir < 4; dir++){
                            if(isStartingPoint(r, c, dir, M)){
                                int i = r + dirs[dir][0], j = c + dirs[dir][1], len = 1;
                                while(i >= 0 && i < R && j >= 0 && j < C && M[i][j] == 1){
                                    len++;
                                    i += dirs[dir][0];
                                    j += dirs[dir][1];
                                }
                                res = Math.max(res, len);
                            }
                        }
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

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