# sorting and normal Python

• Solution 1, annotate the matrix entries with coordinate information so that we can just sort them by that.

def findDiagonalOrder(self, matrix):
entries = [(i+j, (j, i)[(i^j)&1], val)
for i, row in enumerate(matrix)
for j, val in enumerate(row)]
return [e[2] for e in sorted(entries)]

I just saw that @_aig_ does it very similarly, but sorting coordinates. Not sure what I like better.

Solution 2, just walk over the matrix in the desired order. My d is the diagonal number, i.e., i+j. So I can compute j as d-i.

def findDiagonalOrder(self, matrix):
m, n = len(matrix), len(matrix and matrix[0])
return [matrix[i][d-i]
for d in range(m+n-1)
for i in range(max(0, d-n+1), min(d+1, m))[::d%2*2-1]]

Why the range range(max(0, d-n+1), min(d+1, m))? Well I need 0 <= i < m and 0 <= j < n. As said above, j is d-i, so I have 0 <= d-i < n. Isolating i gives me i <= d and i > d-n. Since we're dealing with integers, they're equivalent to i < d+1 and i >= d-n+1. So my i needs to be in the range [0, m) as well as in the range [d-n+1, d+1). And my range is simply the intersection of those two ranges.

• My attempt at Solution 2 in C++, however, I couldn't figure out how Stefan doesn't need the if statement inside the loop.

vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
int nrow=matrix.size(), ncol=matrix.empty() ? 0 : matrix[0].size();
vector<int> out;
for (int d=0; d<nrow+ncol-1; d++) {
if (d%2) for (int i=max(0,d-ncol+1); i<min(d+1,nrow); i++) out.push_back(matrix[i][d-i]);
else for (int i=max(0,d-nrow+1); i<min(d+1,ncol); i++) out.push_back(matrix[d-i][i]);
}
return out;
}

• I couldn't figure out how Stefan doesn't need the if statement inside the loop

Well I need the range range(max(0, d-n+1), min(d+1, m)) either forwards or backwards, depending on d. So I slice it with [::d%2*2-1] which is either [::1] and thus uses the range forwards or [::-1] and thus uses the range backwards.

• hello, Stefan.Would you mind explain the code n=len(matrix and matrix[0]) ? if I use n=len(matrix[0]),it would out of index. But I couldn't figure out why. Could you explain it? Maybe matrix and matrix[0] could deal with some special situations? Thx.

• Similar 1-line solution:

def findDiagonalOrder(self, matrix):
return [matrix[i][j] for i, j in
sorted([(i, j) for i in range(len(matrix)) for j in range(len(matrix[0]))],
key=lambda (i, j): (i + j, (j, i)[(i + j) & 1]))
] if any(matrix) else []

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.