Java solution, easy to understand, O(n), 7ms


  • 2
    D

    There are two key points.
    First, in each path, index row + col == sum. sum is some constant looping from 0 to totalRow + totalCol.
    Second, the boundary of row and col is either sum or four edges. Four edges correspond to row == 0 || row == totalRow - 1 || col == 0 || col == totalCol - 1.

    if{ } block is the only thing we need to figure out. The two tricky parts are "rr = Math.min(sum, r-1)" and "while(rr >= 00 && cc < c)" as I commented in the code.

    public class Solution {
        public int[] findDiagonalOrder(int[][] matrix) {
            if(matrix.length == 0)
                return new int[0];
            int c = matrix[0].length, r = matrix.length;
            int[] res = new int[r*c];
            boolean flip = true;
            int count = 0;
            for(int sum = 0; sum <= r + c - 2; sum++){
                int rr,cc;
                if(flip == true){                               // Direction: to up-right
                    rr = Math.min(sum, r-1);                    // if before diagonal, rr = sum; else rr = r-1
                    cc = sum - rr;
                    while(rr >= 00 && cc < c)                   // reach matrix upper or right bound
                        res[count++] = matrix[rr--][cc++];
                }
                else{                                           // Direction: to bottom-left
                    cc = Math.min(sum, c-1);                    // if before diagonal, cc = sum; else cc = c-1
                    rr = sum - cc;
                    while(cc >= 00 && rr < r)                   // reach matrix bottom or left bound
                        res[count++] = matrix[rr++][cc--];
                }
                flip = !flip;           
            }
            return res;
        }
    }
    

  • 1
    N

    the two tricky parts solved the direction switch problem, easy to figure out.


  • 0
    Z

    said in Java solution, easy to understand, O(n):

    for (int sum = 0; sum <= r + c; sum++)

    why is sum <= r + c? shouldn't it be sum <= r + c - 2?


  • 0
    D

    @zhaoyu92 Yeah, u are right. Those two loops do nothing. I didn't notice that.


Log in to reply
 

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