Solution: Sort the Matrix Diagonally

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #1329 (Medium): Sort the Matrix Diagonally

---

Description:

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

---

Examples:

Example 1:
Input:	mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output:	[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
Visual:

Example 2:
Input:	mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8], [22,27,33,25,68,4],[84,28,14,11,5,50]]
Output:	[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15], [22,27,31,36,50,66],[84,28,75,33,55,68]]

---

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• 1 <= mat[i][j] <= 100

---

Idea:

The easy solution here is to read each diagonal row, then sort it, then write it back again. To read the diagonal line, it can be best to think of the rows as extending out to the left and right.

For a matrix (M) of height y and width x, in order to get all the diagonal rows, we would need to extend out the i values to the left by y - 1 (the corner cell counts as both on the x and y sides). But in this case, we can ignore the first and last diagonal rows, as they only contain one cell each and thus don't need to be sorted. That means that the range of i should be 0 - (y - 2) <= i <= x - 1, or 2 - y <= i <= x - 1.

Then we can just iterate through these diagonals and store the valid cell values in an array (diag). After sorting diag, we can then iterate back through the diagonal and replace the valid cells with the appropriate sorted value.

To avoid complex logic involving matrix bounds, we can just use a fixed dimension for diag along with an index, k. In this case, y represents diag's max length.

---

Implementation:

For Javascript, we can use the faster typed Uint8Array for diag, as the range of cell values is quite small. We can fill it with 101's between iterations so the unused portion of the array stays sorted at the end.

Python has a much more convenient inline list-building capability that we can take advantage of. It'll be easier to just pop() off the elements from diag and start with a brand-new diag on each iteration.

Both Java and C++ will allow us to save time by only having to sort a partial array.

---

Javscript Code:

var diagonalSort = function(M) {
    let y = M.length, x = M[0].length - 1,
        diag = new Uint8Array(y), k
    for (let i = 2 - y; i < x; i++) {
        diag.fill(101), k = 0
        for (let j = 0; j < y; j++)
            if (i+j >= 0 && i+j <= x)
                diag[k++] = M[j][i+j]
        diag.sort(), k = 0
        for (let j = 0; j < y; j++)
            if (i+j >= 0 && i+j <= x)
                M[j][i+j] = diag[k++]
    }
    return M
};

---

Python Code:

class Solution:
    def diagonalSort(self, M: List[List[int]]) -> List[List[int]]:
        y, x = len(M), len(M[0])
        for i in range(2-y, x-1):
            valid = range(max(0, 0-i), min(y, x-i))
            diag, k = sorted([M[j][i+j] for j in valid]), 0
            for j in valid:
                M[j][i+j], k = diag[k], k + 1
        return M

---

Java Code:

class Solution {
    public int[][] diagonalSort(int[][] M) {
        int y = M.length, x = M[0].length - 1;
        int[] diag = new int[y];
        for (int i = 2 - y; i < x; i++) {
            int k = 0;
            for (int j = 0; j < y; j++)
                if (i+j >= 0 && i+j <= x)
                    diag[k++] = M[j][i+j];
            Arrays.sort(diag, 0, k);
            k = 0;
            for (int j = 0; j < y; j++)
                if (i+j >= 0 && i+j <= x)
                    M[j][i+j] = diag[k++];
        }
        return M;
    }
}

---

C++ Code:

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& M) {
        int y = M.size(), x = M[0].size() - 1;
        vector<int> diag(y);
        for (int i = 2 - y; i < x; i++) {
            int k = 0;
            for (int j = 0; j < y; j++)
                if (i+j >= 0 && i+j <= x) {
                    diag[k] = M[j][i+j];
                    k++;
                }
            sort(diag.begin(), diag.begin() + k);
            k = 0;
            for (int j = 0; j < y; j++)
                if (i+j >= 0 && i+j <= x) {
                    M[j][i+j] = diag[k];
                    k++;
                }
        }
        return M;
    }
};