package com.fishercoder.solutions;

/**
 * 498. Diagonal Traverse
 *
 *  Given a matrix of m x N elements (m rows, N columns), return all elements of the matrix in diagonal order
 *  as shown in the below image.

 Example:

 Input:
 [
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
 ]
 Output:  [1,2,4,7,5,3,6,8,9]

 Note:

 The total number of elements of the given matrix will not exceed 10,000.

 */
public class _498 {

public static class Solutoin1 {
    /**
     * Reference: https://discuss.leetcode.com/topic/77865/concise-java-solution/2
     * Just keep walking the matrix, when hitting the four borders (top, bottom, left or right),
     * just directions and keep walking.
     */
    public int[] findDiagonalOrder(int[][] matrix) {

        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[] result = new int[m * n];
        int d = 1;
        int i = 0;
        int j = 0;
        for (int k = 0; k < m * n; ) {
            result[k++] = matrix[i][j];
            i -= d;
            j += d;

            if (i >= m) {
                i = m - 1;
                j += 2;
                d = -d;
            }
            if (j >= n) {
                j = n - 1;
                i += 2;
                d = -d;
            }
            if (i < 0) {
                i = 0;
                d = -d;
            }
            if (j < 0) {
                j = 0;
                d = -d;
            }
        }
        return result;
    }
}

}

@@ -33,369 +33,8 @@
 s;%0A%0A
-/**%0A * 498. Diagonal Traverse%0A *%0A *  Given a matrix of m x N elements (m rows, N columns), return all elements of the matrix in diagonal order%0A *  as shown in the below image.%0A%0A Example:%0A%0A Input:%0A %5B%0A %5B 1, 2, 3 %5D,%0A %5B 4, 5, 6 %5D,%0A %5B 7, 8, 9 %5D%0A %5D%0A Output:  %5B1,2,4,7,5,3,6,8,9%5D%0A%0A Note:%0A%0A The total number of elements of the given matrix will not exceed 10,000.%0A%0A */%0A
 publ
@@ -50,16 +50,20 @@
 _498 %7B%0A%0A
+    
 public s
@@ -94,12 +94,20 @@
     
-/**%0A
+    /**%0A    
     
@@ -190,16 +190,20 @@
 /2%0A     
+    
 * Just k
@@ -286,16 +286,20 @@
 right),%0A
+    
      * j
@@ -340,11 +340,19 @@
     
-*/%0A
+    */%0A    
     
@@ -405,24 +405,28 @@
  %7B%0A%0A        
+    
 if (matrix =
@@ -453,24 +453,28 @@
 gth == 0) %7B%0A
+    
             
@@ -492,34 +492,42 @@
 int%5B0%5D;%0A        
-%7D%0A
+    %7D%0A    
         int m = 
@@ -545,24 +545,28 @@
 th;%0A        
+ 
+   
 int n = matr
@@ -571,32 +571,36 @@
 trix%5B0%5D.length;%0A
+    
         int%5B%5D re
@@ -626,24 +626,28 @@
 n%5D;%0A        
+ 
+   
 int d = 1;%0A 
@@ -641,24 +641,28 @@
  int d = 1;%0A
+    
         int 
@@ -672,24 +672,28 @@
  0;%0A        
+ 
+   
 int j = 0;%0A 
@@ -683,32 +683,36 @@
      int j = 0;%0A
+    
         for (int
@@ -746,16 +746,20 @@
         
+ 
+   
 result%5Bk
@@ -790,16 +790,20 @@
         
+    
 i -= d;%0A
@@ -810,24 +810,28 @@
             
+  
+  
 j += d;%0A%0A   
@@ -827,16 +827,20 @@
  += d;%0A%0A
+    
         
@@ -869,24 +869,28 @@
             
+  
+  
 i = m - 1;%0A 
@@ -900,24 +900,28 @@
             
+    
 j += 2;%0A    
@@ -924,32 +924,36 @@
                 
+  
+  
 d = -d;%0A        
@@ -948,34 +948,40 @@
 -d;%0A            
-%7D%0A
+    %7D%0A  
             if (
@@ -972,24 +972,26 @@
             
+  
 if (j %3E= n) 
@@ -1004,24 +1004,28 @@
             
+    
 j = n - 1;%0A 
@@ -1043,16 +1043,20 @@
     
+   
+ 
 i += 2;%0A
     
@@ -1047,24 +1047,28 @@
     i += 2;%0A
+    
             
@@ -1083,34 +1083,42 @@
 -d;%0A            
+   
+ 
 %7D%0A
+    
             if (
@@ -1142,23 +1142,31 @@
         
+   
+ 
 i = 0;%0A
+    
         
@@ -1185,34 +1185,42 @@
 -d;%0A            
+   
+ 
 %7D%0A
+    
             if (
@@ -1220,32 +1220,36 @@
    if (j %3C 0) %7B%0A
+    
                 
@@ -1267,32 +1267,36 @@
             
+    
 d = -d;%0A
             
@@ -1275,32 +1275,36 @@
         d = -d;%0A
+    
             %7D%0A  
@@ -1301,34 +1301,42 @@
       %7D%0A        
-%7D%0A
+    %7D%0A    
         return r
@@ -1346,15 +1346,23 @@
 lt;%0A    
-%7D%0A
+    %7D%0A    
 %7D%0A%0A%7D%0A

refactor 498