Sort the Matrix Diagonally

Problem Statement

In this task, you are provided with a matrix composed of integers. The matrix is defined by its rows and columns, denoted as m x n. Each element within the matrix belongs to a unique matrix diagonal. A matrix diagonal is a sequence of elements that starts from any cell in the topmost row or the leftmost column, extending in a bottom-right direction until it reaches the boundary of the matrix.

Your objective is to sort each of these matrix diagonals individually in ascending order. Once sorted, you must reassemble these diagonals back into the matrix format to produce and return the newly sorted matrix. The solution should handle any matrix configurations up to a maximum of 100x100 elements and individual element values ranging between 1 and 100.

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

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

Approach and Intuition

To tackle the problem of sorting the diagonals in a given matrix, we need to follow a structured approach:

1. Identify and extract each diagonal of the matrix.

   • Start from every element in the first row and the first column to ensure all diagonals are covered.
   • For each starting element, traverse down to the bottom-right, collecting elements until you reach the edge of the matrix.

2. Sort each of these extracted diagonals.

   • Since the constraints allow a maximum of 100 elements per matrix side, an efficient sorting algorithm like Timsort (used in Python’s built-in sort function) is suitable. This will handle the sorting of diagonals containing up to 100 elements with ease.

3. Place the sorted values back into their respective diagonal positions in the matrix.

   • Carefully map each sorted diagonal back to its original positions in the matrix according to their indices.

This method ensures every diagonal is sorted individually and then reassembled to form the final matrix structure that still adheres to the input matrix dimensions but with diagonals sorted in ascending order. This approach leverages systematic traversal and sorting of partitioned matrix elements, making the problem manageable and the solution efficient within the given constraints.

Solutions

class Solution {
public:
    vector<vector<int>> sortDiagonalMatrix(vector<vector<int>>& matrix) {
        size_t rows = matrix.size();
        size_t cols = matrix[0].size();
    
        for (size_t i = 0; i < rows; i++) {
            arrangeDiagonal(i, 0, matrix);
        }
    
        for (size_t j = 0; j < cols; j++) {
            arrangeDiagonal(0, j, matrix);
        }
    
        return matrix;
    }
    
    vector<int> sortWithCounting(vector<int> elements) {
        int minimum = 1;
        int maximum = 100;
    
        int range = maximum - minimum + 1;
        int count[range] = {0};
    
        for (int element : elements) {
            count[element - minimum]++;
        }
    
        vector<int> sortedElements;
        for (int k = 0; k < range; k++) {
            for (int countTime = count[k]; countTime > 0; countTime--) {
                sortedElements.push_back(k + minimum);
            }
        }
    
        return sortedElements;
    }
    
    void arrangeDiagonal(size_t startRow, size_t startCol, vector<vector<int>>& matrix) {
        size_t rows = matrix.size();
        size_t cols = matrix[0].size();
    
        vector<int> diagonal;
    
        size_t length = min(rows - startRow, cols - startCol);
        for (size_t l = 0; l < length; l++) {
            diagonal.push_back(matrix[startRow + l][startCol + l]);
        }
    
        sort(diagonal.begin(), diagonal.end());
    
        for (size_t l = 0; l < length; l++) {
            matrix[startRow + l][startCol + l] = diagonal[l];
        }
    }
};