Anti Diagonals

Give a N*N square matrix, return an array of its anti-diagonals.

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

Approach : The point to observe here is that the sum of i (row number) and j (column number) is constant for each anti-diagonal.
For example:
Diagonal 1 has i + j = 0
Diagonal 2 has i + j = 1 
and so on.
So define s = i + j
Loop with s from 0 to 2*(N-1) (maximum sum possible) 
Now if s = i+j then j = s-i 
So we have reduced the problem to two variables: s and i (O(n^2)).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

vector<vector<int> > Solution::diagonal(vector<vector<int> > &A) { vector<vector<int>> result; vector<int> diagonal; int n = A.size(); if(n == 0) return result; for(int d = 0; d <= 2*(n-1); d++) { for(int i = 0; i <= d; i++) { int j = d - i; //continue if i or j exceeds their bounds if(i >= n || j >= n) continue; diagonal.push_back(A[i][j]); } result.push_back(diagonal); diagonal.clear(); } return result; }