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.lengthn == mat[i].length1 <= m, n <= 1001 <= 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:
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.
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.
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
- C++
- Java
- Python
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];
}
}
};
Sort the Matrix Diagonally in C++
The provided C++ solution sorts each diagonal of a matrix independently from the top-left to the bottom right. Here’s a structured explanation of how the solution works:
- Extract the number of rows (
rows) and columns (cols) from the matrix. - Loop through each element starting from the first row, using the function
arrangeDiagonalto sort the diagonal starting at the indicated row and the first column. - Repeat the diagonal sorting for each column starting from the first row.
- The
arrangeDiagonalfunction collects all elements along a diagonal, sorts them, and then places them back into their original positions in the matrix. - The diagonal collection is determined by the smaller dimension from the starting point either downward or rightward.
- Sorting is done using the standard library sort function.
The sortWithCounting function, though defined, is not used in the main algorithm; it demonstrates how to sort an array using the Counting Sort method but is not integrated into the solution for sorting the diagonals.
Ensure to include the <vector> and <algorithm> libraries in your code to make use of the vector container and sort function, respectively.
The resulting matrix is returned, now with each diagonal sorted numerically from smallest to largest, enhancing readability and order within the matrix structure.
class SortMatrixDiagonals {
public int[][] sortDiagonals(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
for (int r = 0; r < rows; r++) {
sortDiagonalHelper(r, 0, matrix);
}
for (int c = 1; c < cols; c++) {
sortDiagonalHelper(0, c, matrix);
}
return matrix;
}
private List<Integer> performCountingSort(List<Integer> diagElements) {
int minimum = 1;
int maximum = 100;
int range = maximum - minimum + 1;
int[] bucket = new int[range];
for (int number : diagElements) {
bucket[number - minimum]++;
}
List<Integer> sortedDiag = new ArrayList<>();
for (int i = 0; i < range; i++) {
while (bucket[i] > 0) {
sortedDiag.add(i + minimum);
bucket[i]--;
}
}
return sortedDiag;
}
private void sortDiagonalHelper(int rowStart, int colStart, int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
List<Integer> diagonalValues = new ArrayList<>();
int lengthDiagonal = Math.min(rows - rowStart, cols - colStart);
for (int i = 0; i < lengthDiagonal; i++) {
diagonalValues.add(matrix[rowStart + i][colStart + i]);
}
diagonalValues = performCountingSort(diagonalValues);
for (int i = 0; i < lengthDiagonal; i++) {
matrix[rowStart + i][colStart + i] = diagonalValues.get(i);
}
}
}
The provided Java code efficiently sorts the diagonals of a given matrix. Here’s a concise breakdown of how the program operates:
The
sortDiagonalsmethod initiates the diagonal sorting process. It begins by sorting each diagonal starting from every row of the first column. Then, it sorts each diagonal starting from the first row of every subsequent column.The helper method
sortDiagonalHelperextracts the elements of each diagonal from the matrix based on the starting row and column indices provided. It then sorts these elements using theperformCountingSortmethod, which implements counting sort suitable for the defined range of matrix values.performCountingSorttailors the counting sort algorithm for sorting the values of the diagonal. It assumes that the values fall within a specified minimum and maximum, thus enhancing sorting efficiency within a controlled value range.Once sorted,
sortDiagonalHelperplaces the sorted values back into their corresponding positions in the original matrix diagonals.
By following the above methods, the matrix diagonals are sorted individually, leading to the final arrangement where each diagonal of the matrix is ordered from the smallest to the largest element. This allows the sorted matrix to retain organized diagonal sequences.
class Solution:
def sortDiagonals(self, matrix: List[List[int]]) -> List[List[int]]:
rows = len(matrix)
cols = len(matrix[0])
# Helper function to sort a given diagonal specified by start_row and start_col
def sort_diag(start_row, start_col):
diag_elements = []
diag_len = min(rows - start_row, cols - start_col)
# Collect diagonal elements from matrix
for k in range(diag_len):
diag_elements.append(matrix[start_row + k][start_col + k])
# Apply counting sort to the diagonal elements
diag_elements = applyCountingSort(diag_elements)
# Place sorted values back into the matrix
for k in range(diag_len):
matrix[start_row + k][start_col + k] = diag_elements[k]
# Create counting sort for the diagonal elements
def applyCountingSort(diagonal_vals):
# Assuming matrix values between 1 and 100 (inclusive)
min_val = 1
max_val = 100
count = Counter(diagonal_vals)
# Flatten counts into a sorted array
sorted_values = []
for num in range(min_val, max_val + 1):
sorted_values.extend([num] * count[num])
return sorted_values
# Process all diagonals starting from each row of the first column
for start_row in range(rows):
sort_diag(start_row, 0)
# Process all diagonals starting from each column of the first row
for start_col in range(1, cols):
sort_diag(0, start_col)
return matrix
The provided Python program implements a function to sort the diagonals of a given matrix. The function, sortDiagonals, sorts each diagonal individually and then places the sorted values back into the matrix at their respective positions.
Here's how the sorting process operates:
- The program defines a helper function,
sort_diag, responsible for collecting, sorting, and reintegrating the elements of a specific diagonal back into the matrix. - Diagonal elements are collected using a for loop, starting from a given
start_rowandstart_col. - Sorting the extracted diagonal elements is accomplished by calling another helper function,
applyCountingSort. - The
applyCountingSortfunction utilizes the Counting Sort algorithm, assuming that the matrix values range between 1 and 100. It counts instances of each value and produces a sorted list of diagonal values. - The sorted diagonal values are then placed back into their original positions in the matrix.
- The program iterates through all possible starting positions for diagonals along the first row and the first column using two separate for loops.
- For each starting position on the first column, it calls
sort_diagwith increasing row indices while keeping the column index at 0. - Similarly, it processes diagonals beginning in different columns of the first row by keeping the row index at 0 and increasing the column index.
- For each starting position on the first column, it calls
This approach ensures that all matrix diagonals, both starting from every row of the first column and from every column of the top row, get sorted independently. The result is a matrix with sorted diagonals returned by the main function sortDiagonals.
No comments yet.