DEV Community

loading...
Cover image for Solution: Sort the Matrix Diagonally

Solution: Sort the Matrix Diagonally

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
・4 min read

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 1 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.

image

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
};
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)