Return the anti-diagonals
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:


define the variables with interface types: List&lt;List&lt;Integer&gt;&gt; ans = new ArrayList&lt;&gt;(); this includes method arguments and return value.  This will allow you to change concrete implementation with minimal changes.
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));
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)
naming conventions: variables start with lower case.