Solution: Sort the Matrix Diagonally
Tags: algorithms, javascript, java, python
Published: 2021-02-15 05:43:20

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/sort-the-matrix-diagonally/discuss/1030744).*

---

####[Leetcode Problem #1329 (*Medium*): Sort the Matrix Diagonally](https://leetcode.com/problems/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 1 Visual](https://assets.leetcode.com/uploads/2020/01/21/1482_example_1_2.png)

Example 2:||
|---:|---|
*Input:*|mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],<br>[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],<br>[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.

![image](https://assets.leetcode.com/users/images/b9f08eb1-9414-4956-af4e-bd3ef5edcf59_1611396909.7399392.png)

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:***
```javascript
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:***
```python
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:***
```java
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:***
```c++
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;
    }
};
```