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]
Explanation:

Note:

  1. The total number of elements of the given matrix will not exceed 10,000.
/**
public class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return new int[0];
        int row = 0;
        int col = 0;
        int tag = 1;
        int m = matrix.length;
        int n = matrix[0].length;
        int[] result = new int[m * n];
        for (int i = 0; i < m * n; i++) {
result[i] = matrix[row][col];
row -= tag;
col += tag;
// Should pay attention to the other of checking 0 and m/n bound.
// Should check m/n bound first, or tag willl be reversed twice.
// row/col should plus 2 rather than 1 in this case.
if (row > m - 1) {row = m - 1; col += 2; tag = -tag;}
            if (col > n - 1) {col = n - 1; row += 2; tag = -tag;}
            if (row < 0) {row = 0; tag = -tag;}
            if (col < 0) {col = 0; tag = -tag;}
        }
        return result;
    }
}
*/
// Solution 2: instead using tag directly, we can also use a dictionary.
public class Solution {
    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 row = 0;
        int col = 0;
        int tag = 0;
        int[][] dict = {{-1, 1}, {1, -1}};
        int[] result = new int[m * n];

        for (int i = 0; i < m * n; i++) {
result[i] = matrix[row][col];
row += dict[tag][0];
col += dict[tag][1];
if (row > m - 1) {row = m - 1; col += 2; tag = 1 - tag;}
             if (col > n - 1) {col = n - 1; row += 2; tag = 1 - tag;}
             if (row < 0) {row = 0; tag = 1 - tag;}
             if (col < 0) {col = 0; tag = 1 - tag;}
}
return result;
}
}

/* In the onsite inteview from Bloomberg, I came across a similar problem, instead of traverse with two directions,
the oder in the problem I came across is from bottom left to upper right for each diagnal traversal,
the code can be like the following: */
public class Solution {     // The order of each diagonal traversal is bottom left -> upper right.
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return new int[0];
        int m = matrix.length - 1;
        int n = matrix[0].length - 1;
        int[] result = new int[(m + 1) * (n + 1)];
        int row = 0;
        int col = 0;
        int index = 0;
        for (int sum = 0; sum <= m + n; sum++) {
// row = sum > m ? m : sum;
            row = Math.min(sum, m);
            col = sum - row;
            while (row >= 0 && col <= n) {
                result[index++] = matrix[row--][col++];
                // The following lines can be combined to the single line above.
//                 result[index] = matrix[row][col];
//                 row -= 1;
//                 col += 1;
//                 index++;
            }
        }
        return result;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s