# Return the 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]
]


This is my approach to this question:

public class Solution {
public ArrayList<ArrayList<Integer>> diagonal(ArrayList<ArrayList<Integer>> A) {

//The total number of internal rows in the final list will be 2*noofrows(A) - 1
int size = 2*A.get(0).size() - 1;
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
int count = 0;

//Count of the number of rows
int r = A.size();

//Time complexity: O(size*r^2)
//Space complexity: O(size)
while( count < size)
{
ArrayList<Integer> temp = new ArrayList<>();
for( int i = 0; i < r; i++ )
{
for( int j = 0; j < r; j++ )
{
if( ((i + j) == count))

//Continue when the indices sum up to be > count
if((i + j) > count )
continue;
}
}
count++;
}
return ans;
}


I have the following questions regarding my code:

1) Is there any better approach to solve this problem?

2) How can I improve my time and space complexity?

3) Are there any redundant steps that can be removed?

Reference

• is there any special reason why you give ArrayList<ArrayList<Integer>> as input parameter - instead of a plain mere int[][] ? Feb 19, 2018 at 5:09
• It was a question asked in an interview. I don't know the exact reason but I think it is to allow dynamical storage of elements. Feb 19, 2018 at 9:08

I figured out a solution that improves on time complexity:
So here's the thing: the solution is actually a rearrangement of the matrix, meaning O(r^2) should be possible: visit each cell of the matrix once, determinig its location in the solution.

and it's straightforward: find the heads of the anti-diagonals, and for each one, find all its members.
finding the heads: iterate over the first row, then (when you reached end of row) iterate over the last column.
for each cell in above mentioned iteration, start gathering anti-diagonal members by advancing one row down, one column left, until either one goes beyond matrix' bounds.

few notes on the posted code:

1. define the variables with interface types: List<List<Integer>> ans = new ArrayList<>(); this includes method arguments and return value. This will allow you to change concrete implementation with minimal changes.

2. use short form if (without braces) judiciously. it makes the code less clear and is prone to errors. Some ppl will say do not use this at all. when I use it, I put the condition and action in the same line:
if( ((i + j) == count)) temp.add(A.get(i).get(j));

3. I think in these types of questions, where input is known and does not change, arrays are bettter suited then Collections, since they offer more concise syntax: A[i][j] is more clear then A.get(i).get(j)

• Thanks, @Sharon. I did not think of this approach. With 1, it was showing me an error that ' List<List> != ArrayList<ArrayList ' . Also, the input given to me was an ' ArrayList<ArrayList>Integer>> ', so I did not think about converting this into a 2 array. Feb 18, 2018 at 3:40
• yes, you must match the argument and return types. whoever wrote the method signature should be informed Feb 18, 2018 at 5:52

why don't you try to keep your algorithm as easy as possible?

• one thing to keep things simple is to use an int[][] as source
• you can directly calculate the length of each diagonal
• you can directly calculate the indice (x/y) of each element of the diagonal
• you can calculate the diagonal from the top and from the right in one step
• if you init your result you can simply set the diagonales at it's index

1. Is there any better approach to solve this problem?
=> it's more clean if you don't use Lists when it's not required, better use primitives
2. How can I improve my time and space complexity?
=> you can skip iteration over the matrix if you calculate indice directly
3. Are there any redundant steps that can be removed?
=> no code is redundant, the algorithm (see above) is redundant and already fixed

int [][] src = ...
int n = src.length; //it's n because it's an N x N-Matrix
List<Integer[]> result = new ArrayList<>(n);
for (int i = 0; i < 2*n-1; i ++){
}
for (int c = 0; c < n; c ++){ //c = column
Integer [] diagonalTop = new Integer[c+1];
Integer [] diagonalRight = new Integer[c+1];
for(int s = 0; s <= c; s++){//s = step in diagonal
int xTop = c-s;
int yTop = c-xTop;
int xRight = n-s-1;
int yRight = n - c + s -1;
diagonalTop[c-s] = Integer.valueOf(src[xTop][yTop]);
diagonalRight[s] = Integer.valueOf(src[yRight][xRight]);
}
result.set(c,diagonalTop ); //adding (setting) at the proper index
if(c < n-1){
result.set(2*n-c-2, diagonalRight ); //adding (setting) at the proper index
}
}

• This answer has some reasonable comments, but the code should not be held up as an example of how to write it. result = new ArrayList<>(n); is too small - and given that you're arguing for int[][] it's unclear why you want to use List<Integer[]> here. null would work as well as new Integer[] {} to pad it to the right length, and would also create less garbage and be less misleading when examining the state in a debugger. If it's necessary to add comments like //c = column then the variable has the wrong name. Feb 19, 2018 at 15:29
• yes (+1@PeterTaylor) my intention was to point out that both diagonals can be calculated in one step... i was a bit too enthusiastic and added too much code - that was not necessarily and lead to a misleading interpretation (thanks for bringing that out) Feb 20, 2018 at 5:02
        //The total number of internal rows in the final list will be 2*noofrows(A) - 1
int size = 2*A.get(0).size() - 1;
...

//Count of the number of rows
int r = A.size();


Is the number of rows A.get(0).size() or A.size()? Yes, they're the same (because the spec says that the matrix is square), but the comments are actively confusing, and it matters because the direction of the antidiagonals depends on whether the first index is the row or the column.

What's your indentation convention? Whatever it is, this code doesn't seem to follow it consistently. Sometimes the braces are indented relative to their controlling while / for, and sometimes they aren't.

                    for( int j = 0; j < r; j++ )
{
if( ((i + j) == count))

//Continue when the indices sum up to be > count
if((i + j) > count )
continue;
}


Two things:

Firstly, a continue; statement at the end of a loop does precisely nothing. This code is directly equivalent to

                    for( int j = 0; j < r; j++ )
{
if( ((i + j) == count))
}


I think you wanted either a break; or a named continue - but the latter should be used very rarely because it's not often the clearest way to structure code.

Secondly, how would you optimise the following code?

for (int k = 0; k < 100; k++)
{
if (k == 17) System.out.println(myArray[k]);
}


System.out.println(myArray[17]);
The same principle applies to the loop over j.