Java: Easy to understand O(MN) solution with comments


  • 1
    M
    public class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if(matrix == null) return new int[0];
        int m = matrix.length;
        if(m == 0) return new int[0];
        int n = matrix[0].length;
        if(n == 0) return new int[0];
        
        int[] result = new int[m * n];
        int i = 0, j = 0, k = 0;
        boolean incr = true;
        
        // Is it a row or column vector?
        if(m == 1 || n == 1){
            for(int r = 0; r < m; ++r)
                for (int c = 0; c < n; ++c)
                    result[k++] = matrix[r][c];    
            return result;
        }
        while(i < m && j < n){
            result[k++] = matrix[i][j];   
            // Is it corner (0, 0)?
            if(i == 0 && j == 0){
                j++;
                incr = !incr;
                continue;
            }
            // Is it corner (m-1, 0)?
            if(i == m - 1 && j == 0){
                if(!incr){
                    j++;
                    incr = !incr;
                    continue;
                }
            }
            // Is it corner (0, n-1)?
            if(i == 0 && j == n - 1){
                if(incr){
                    i++;
                    incr = !incr;
                    continue;
                }
            }
            // Is it edges left or bottom?
            if(incr && (i == 0 || j == n - 1)){
                if(i == 0 && j < n - 1){
                    j++;
                }
                else if(i > 0 && j == n - 1){
                    i++;
                }
                else if(i == 0 && j == n - 1){
                    i++;
                }
                incr = !incr;
                continue;
            }
            // Is it edges right or top?
            if(!incr && (j == 0 || i == m - 1)){
                if(j == 0 && i < m - 1){
                    i++;
                }
                else if(j > 0 && i == m - 1){
                    j++;
                }
                else if(i == 0 && i == m - 1){
                    j++;
                }
                incr = !incr;
                continue;
            }
            if(incr){
                    i--;
                    j++;
            }
            else {
                i++;
                j--;
            }
        }
        return result;
    }
    }

Log in to reply
 

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