Concise Java Solution


  • 42

    I don't think this is a hard problem. It is easy to figure out the walk pattern. Anyway...
    Walk patterns:

    • If out of bottom border (row >= m) then row = m - 1; col += 2; change walk direction.
    • if out of right border (col >= n) then col = n - 1; row += 2; change walk direction.
    • if out of top border (row < 0) then row = 0; change walk direction.
    • if out of left border (col < 0) then col = 0; change walk direction.
    • Otherwise, just go along with the current direction.

    Time complexity: O(m * n), m = number of rows, n = number of columns.
    Space complexity: O(1).

    public class Solution {
        public int[] findDiagonalOrder(int[][] matrix) {
            if (matrix == null || matrix.length == 0) return new int[0];
            int m = matrix.length, n = matrix[0].length;
            
            int[] result = new int[m * n];
            int row = 0, col = 0, d = 0;
            int[][] dirs = {{-1, 1}, {1, -1}};
            
            for (int i = 0; i < m * n; i++) {
                result[i] = matrix[row][col];
                row += dirs[d][0];
                col += dirs[d][1];
                
                if (row >= m) { row = m - 1; col += 2; d = 1 - d;}
                if (col >= n) { col = n - 1; row += 2; d = 1 - d;}
                if (row < 0)  { row = 0; d = 1 - d;}
                if (col < 0)  { col = 0; d = 1 - d;}
            }
            
            return result;
        }
    }
    

  • 23

    No need for the dirs array, you can just alternate d between 1 and -1 and add/subtract it.

    public class Solution {
        public int[] findDiagonalOrder(int[][] matrix) {
            if (matrix == null || matrix.length == 0) return new int[0];
            int m = matrix.length, n = matrix[0].length;
            
            int[] result = new int[m * n];
            int row = 0, col = 0, d = 1;
    
            for (int i = 0; i < m * n; i++) {
                result[i] = matrix[row][col];
                row -= d;
                col += d;
                
                if (row >= m) { row = m - 1; col += 2; d = -d;}
                if (col >= n) { col = n - 1; row += 2; d = -d;}
                if (row < 0)  { row = 0; d = -d;}
                if (col < 0)  { col = 0; d = -d;}
            }
            
            return result;
        }
    }
    

  • 0

    @StefanPochmann Haha, you are right. Every time you can find a more concise way :)


  • 8
    Y

    @StefanPochmann
    No need for d version

        public int[] findDiagonalOrder(int[][] matrix) {
            if (matrix.length == 0) return new int[0];
            int r = 0, c = 0, m = matrix.length, n = matrix[0].length, arr[] = new int[m * n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = matrix[r][c];
                if ((r + c) % 2 == 0) { // moving up
                    if      (c == n - 1) { r++; }
                    else if (r == 0)     { c++; }
                    else            { r--; c++; }
                } else {                // moving down
                    if      (r == m - 1) { c++; }
                    else if (c == 0)     { r++; }
                    else            { r++; c--; }
                }   
            }   
            return arr;
        }
    

  • 1
    Q

    @shawngao but your code is more readable ^_^, sometimes it's more important. the code without dirs seems a little tricky playing with d.


  • 5

    I want to point out that the ordering of these part is important:

            if (row >= m) { row = m - 1; col += 2; d = 1 - d;}
            if (col >= n) { col = n - 1; row += 2; d = 1 - d;}
            if (row < 0)  { row = 0; d = 1 - d;}
            if (col < 0)  { col = 0; d = 1 - d;}
    

    If you switch it, you will get an error, like below:

            if (row < 0)  { row = 0; d = 1 - d;}
            if (col < 0)  { col = 0; d = 1 - d;}
            if (row >= m) { row = m - 1; col += 2; d = 1 - d;}
            if (col >= n) { col = n - 1; row += 2; d = 1 - d;}

  • 1
    J

    @Chidong
    Do you know why?


  • 1

    Why the space complexity is O(1) since the result is an array with length of m*n?


  • 0

    @eat_watermelon

        int row = 0, col = 0, d = 0;   
        int[][] dirs = {{-1, 1}, {1, -1}};
    

    This is constant space. The space used to save the result doesn't count in algorithm's space analysis.


  • 0

    @zzhai Got it. Thank you!


  • 2

    Could also be done in a more concise way:

    int[] findDiagonalOrder(int[][] m) {
      int[] result = new int[(m.length == 0) ? 0 : m.length * m[0].length];
      for (int d = 0, i = 0; i < result.length; d++)
        for (int lo = d - min(d, m.length - 1), hi = min(d, m[0].length - 1); lo <= hi; )
          result[i++] = ((d & 1) == 0) ? m[d - lo][lo++] : m[d - hi][hi--];
      return result;
    }
    

    https://discuss.leetcode.com/topic/81022/5-lines-of-java


  • 0
    M

    The important of the order of the “if”
    condition is that you can think about the top right corner and the bottom left corner.These 2 points belong to two of below situation


  • 0
    A

    @StefanPochmann - How come order of "if" conditions are making difference, not getting that. Can you please help.


  • 0
    D

    @Chidong Please explain why the order is important.


  • 0
    M
    This post is deleted!

  • 0
    M
    This post is deleted!

  • 1
    M

    @jtee
    when the pointer reaches the last row/col, we do three things:

    1. override row/col to m - 1 or n - 1
    2. add 2 to the col/row
      This can make col/row positive and therefore skip the 3rd or 4th loop.
    3. switch direction

  • 2
    M

    Order of "if " is key here...... for example if you put

     if (row < 0)  { row = 0; d = -d;}
    

    as the first condition then in 3x3 matrix when you reach at (0,2), your row and col become -1, 3 respectively. So going through all the if conditions will make you point to (2,2) rather than (1,2),

    making your traversal wrong and thereafter in next iteration resulting in ArrayIndexOutOfBoundsExcetion as it would look for (3,2).


  • 0

    Without using magic number

    public int[] findDiagonalOrder(int[][] matrix) {
      int m = matrix.length;
      if(m == 0) return new int[0];   
      int n = matrix[0].length;
      int[] res = new int[m * n];
      String dir = "RU";
      int r = 0, c = 0;
      for(int i = 0; i < m * n; i++){
        res[i] = matrix[r][c];
        if(dir.equals("RU")){
          r--;
          c++;
        } else {
          r++;
          c--;
        }
    
        if(r >= m) {
          r = m - 1;
          c += 2;
          dir = "RU";
        }
        if(c >= n) {
          c = n - 1;
          r += 2;
          dir = "LD";
        }
        if(r < 0){
          r = 0;
          dir = "LD";
        }
        if(c < 0){
          c = 0;
          dir = "RU";
        }
      } 
      return res;
    }

Log in to reply
 

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