sorting and normal Python

  • 8

    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.

  • 0

    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;

  • 0

    @baselRus said in sorting and normal Python:

    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.

  • 0

    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.

  • 0

    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 []

Log in to reply

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