Leetcode 1329: Sort the Matrix Diagonally
You are given a matrix
mat of integers with dimensions m x n. A matrix diagonal is a sequence of matrix elements that start from some cell in the topmost row or leftmost column and go diagonally towards the bottom-right corner. Your task is to sort each matrix diagonal in ascending order and return the resulting matrix.Problem
Approach
Steps
Complexity
Input: The input consists of a 2D integer matrix `mat` of dimensions `m x n`.
Example: For example, given mat = [[5, 9, 3], [8, 6, 1], [7, 4, 2]], the task is to sort each diagonal of this matrix.
Constraints:
• 1 <= m, n <= 100
• 1 <= mat[i][j] <= 100
Output: The output should be the matrix where each diagonal is sorted in ascending order.
Example: For mat = [[5, 9, 3], [8, 6, 1], [7, 4, 2]], the output would be [[1, 3, 2], [4, 5, 1], [7, 6, 9]].
Constraints:
Goal: Sort the elements along each diagonal of the matrix in ascending order while keeping the relative positions of the diagonals unchanged.
Steps:
• 1. Identify all diagonals in the matrix.
• 2. For each diagonal, store the elements and sort them in ascending order.
• 3. Replace the original elements of each diagonal with the sorted values.
• 4. Return the modified matrix.
Goal: The input matrix `mat` will have at least one row and one column, and the matrix values are constrained by the size limits.
Steps:
• 1 <= m, n <= 100
• 1 <= mat[i][j] <= 100
Assumptions:
• The matrix is not empty, and each element is an integer between 1 and 100.
• Input: Input: mat = [[5, 9, 3], [8, 6, 1], [7, 4, 2]]
• Explanation: The diagonals are [5], [9, 8], [3, 6, 7], [1, 4], and [2]. After sorting each diagonal, we get the matrix [[1, 3, 2], [4, 5, 1], [7, 6, 9]].
• Input: Input: mat = [[10, 21, 30], [4, 15, 24], [5, 6, 23]]
• Explanation: The diagonals are [10], [21, 4], [30, 15, 5], [24, 6], and [23]. After sorting each diagonal, we get the matrix [[4, 15, 23], [5, 21, 30], [10, 6, 24]].
Approach: The algorithm extracts the elements along each diagonal, sorts them, and then places the sorted values back in the matrix, preserving the original structure of the matrix.
Observations:
• Each diagonal is independent and can be sorted individually.
• We need to identify and extract diagonals before sorting them and placing the sorted values back into the matrix.
Steps:
• 1. Traverse the matrix to extract all the diagonals.
• 2. Sort each diagonal independently.
• 3. Replace the original diagonal elements with the sorted ones.
• 4. Return the resulting matrix.
Empty Inputs:
• An empty matrix will not be provided based on the problem constraints.
Large Inputs:
• The matrix could be as large as 100x100, but the solution should still be efficient.
Special Values:
• When all elements in a diagonal are the same, the diagonal will remain unchanged after sorting.
Constraints:
• The matrix has at least one row and column, and each element is between 1 and 100.
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
map<int, priority_queue<int, vector<int>, greater<int>>> mp;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
mp[i-j].push(mat[i][j]);
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++) {
mat[i][j] = mp[i-j].top();
mp[i-j].pop();
}
return mat;
}
1 : Function Declaration
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
This line declares the 'diagonalSort' function that takes a 2D matrix 'mat' as input and returns the matrix with diagonals sorted in ascending order.
2 : Matrix Dimensions Calculation
int m = mat.size(), n = mat[0].size();
The dimensions of the matrix are calculated, where 'm' is the number of rows and 'n' is the number of columns.
3 : Priority Queue Declaration
map<int, priority_queue<int, vector<int>, greater<int>>> mp;
A map 'mp' is declared where the keys represent the diagonals (calculated by the difference 'i-j'), and the values are priority queues that store the diagonal elements in ascending order.
4 : Outer Loop - Row Iteration
for(int i = 0; i < m; i++)
The outer loop iterates over each row of the matrix.
5 : Inner Loop - Column Iteration
for(int j = 0; j < n; j++)
The inner loop iterates over each column in the current row.
6 : Push Diagonal Element into Queue
mp[i-j].push(mat[i][j]);
The element at position (i, j) is pushed into the priority queue corresponding to the diagonal (i-j).
7 : Reprocess Matrix with Sorted Diagonals
for(int i = 0; i < m; i++)
The second loop starts to reprocess the matrix and fill each diagonal with sorted elements.
8 : Set Sorted Diagonal Element
for(int j = 0; j < n; j++) {
This inner loop iterates through each column of the current row to replace the matrix elements with the sorted elements from the corresponding priority queue.
9 : Replace Element with Sorted Value
mat[i][j] = mp[i-j].top();
The top element (smallest element) from the priority queue for the current diagonal is placed into the matrix at position (i, j).
10 : Pop the Used Element
mp[i-j].pop();
After placing the smallest element into the matrix, it is removed from the priority queue for the current diagonal.
11 : Return Sorted Matrix
return mat;
The sorted matrix is returned after all diagonals have been processed and updated.
Best Case: O(m * n * log(m))
Average Case: O(m * n * log(m))
Worst Case: O(m * n * log(m))
Description: The best, average, and worst cases all involve sorting each diagonal, which requires sorting a maximum of m elements.
Best Case: O(m * n)
Worst Case: O(m * n)
Description: The space complexity is O(m * n) due to storing the diagonals and the original matrix.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus