Anti Diagonals

Give a N*N square matrix, return an array of its anti-diagonals. Look at the example for more details.

Example:

		
Input: 	

1 2 3
4 5 6
7 8 9

Return the following :

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



Input : 
1 2
3 4

Return the following  : 

[
  [1],
  [2, 3],
  [4]
]
思路:

先找到diagonal的头，然后从右上角往左下角print。

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    public ArrayList<ArrayList<Integer>> diagonal(ArrayList<ArrayList<Integer>> A) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int len = A.size() * 2 - 1;
        for (int k = 0; k < len; k ++) {
            int i, j;
            if (k < A.size()) {
                i = 0;
                j = k;
            } else {
                i = k - A.size() + 1;
                j = A.size() - 1;
            }
            ArrayList<Integer> row = new ArrayList<>();
            int rowLen;
            if (k < A.size()) {
                rowLen = k + 1;
            } else {
                rowLen = len - k;
            }
            for (int v = 0; v < rowLen; v ++) {
                row.add(A.get(i + v).get(j - v));
            }
            result.add(row);
        }
        return result;
    }
}