3
\$\begingroup\$

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))
                                temp.add(A.get(i).get(j));

                            //Continue when the indices sum up to be > count
                            if((i + j) > count )
                                continue;
                        }
                }
                ans.add(temp);
                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

\$\endgroup\$
  • \$\begingroup\$ is there any special reason why you give ArrayList<ArrayList<Integer>> as input parameter - instead of a plain mere int[][] ? \$\endgroup\$ – Martin Frank Feb 19 '18 at 5:09
  • \$\begingroup\$ 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. \$\endgroup\$ – Anirudh Thatipelli Feb 19 '18 at 9:08
1
\$\begingroup\$

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)

  4. naming conventions: variables start with lower case.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Anirudh Thatipelli Feb 18 '18 at 3:40
  • \$\begingroup\$ yes, you must match the argument and return types. whoever wrote the method signature should be informed \$\endgroup\$ – Sharon Ben Asher Feb 18 '18 at 5:52
1
\$\begingroup\$

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

that leads to answers on your question:

  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 ++){
    result.add(new Integer[]{}); //initialize the result
}
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
    }
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Feb 19 '18 at 15:29
  • \$\begingroup\$ 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) \$\endgroup\$ – Martin Frank Feb 20 '18 at 5:02
1
\$\begingroup\$
        //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))
                                temp.add(A.get(i).get(j));

                            //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))
                                temp.add(A.get(i).get(j));
                        }

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]);
}

Spoiler alert:

System.out.println(myArray[17]);

The same principle applies to the loop over j.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks, @Peter. You are correct that A.get(0).size() is equivalent to A.size(). \$\endgroup\$ – Anirudh Thatipelli Feb 19 '18 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.