Good morning. It is Sunday again. I woke up around 05:00 AM and the outside temperature was -17 F. We are finally experiencing cold winter days in the Twin Cities of Minneapolis and St. Paul. An added bonus for football fans is that today is Super Bowl LV. My wife and I are not sports fans. We like to bike and walk and occasionally scuba dive. Up to a couple years ago we would watch the half time show. We so not watch TV any more. Perhaps we will find the half time show on YouTube.
The main subject for this post is LeetCode 1329 Sort the Matrix Diagonally problem. If interested please visit the associated website to get the information directly from the source. It seems that with time problems are edited to make them more appealing.
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. Constraints: o m == mat.length o n == mat[i].length o 1 <= m, n <= 100 o 1 <= mat[i][j] <= 100
The idea is to sort diagonally the contents of a matrix which may or may not be square. The description seems to be quite good. It helps to draw a few matrices of different sizes on a piece of paper and figure an approach. Once you have a base solution you can improve on its performance.
I will solve the problem using the Java programming language on a Windows 10 computer using the VSCode IDE. You are welcome to solve it any way you feel most comfortable. The simplest approach is to solve the problem on the LeetCode site using the IDE they provide. I have noticed that with time the IDE seems to get better.
Since I decided to solve the problem on my computer I will need to develop a test scaffolding to collect the input data, call the method of interest and display the results. SUCH CODE IS NOT PART OF THE SOLUTION.
public int[][] diagonalSort(int[][] mat) {
}
The signature for the method of interest is simple. The matrix is provided as an argument. We need to return the diagonally sorted version of the matrix.
1,1 7 main <<< rows: 1 cols: 1 main <<< mat: [7] main <<< result: [7] 1,3 6,3,8 main <<< rows: 1 cols: 3 main <<< mat: [6, 3, 8] main <<< result: [6, 3, 8] 3,1 6 3 8 main <<< rows: 3 cols: 1 main <<< mat: [6] [3] [8] main <<< result: [6] [3] [8] 3,4 3,3,1,1 2,2,1,2 1,1,1,2 main <<< rows: 3 cols: 4 main <<< mat: [3, 3, 1, 1] [2, 2, 1, 2] [1, 1, 1, 2] main <<< result: [1, 1, 1, 1] [1, 2, 2, 2] [1, 2, 3, 3] 4,3 3,2,1 3,2,1 1,1,1 1,2,2 main <<< rows: 4 cols: 3 main <<< mat: [3, 2, 1] [3, 2, 1] [1, 1, 1] [1, 2, 2] main <<< result: [1, 1, 1] [1, 2, 2] [1, 2, 3] [1, 2, 3] 5,6 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 main <<< rows: 5 cols: 6 main <<< 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] main <<< result: [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]
The LeetCode site provides two examples. They are included in the set. The first three are mine to check end conditions. The fifth test case was generated to check end conditions. It is the fourth test case with the dimensions swapped.
It seems that our test scaffolding which IS NOT PART OF THE SOLUTION, is presented with the dimensions of the matrix followed by lines of integers each associated with a row for the matrix. Our test scaffolding seems to read the input data and displays the number of rows and columns followed by the actual matrix.
With the matrix on hand, it seems that the method of interest is called and the results are displayed. As we will see in a few, I decided on two similar approaches. To be honest with you, the approach with the priority queue seemed like the first approach, but I decided to go with an array list and then, to improve performance, I used a priority queue.
/**
* Test scaffolding
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read matrix dimensions ****
int[] rowCol = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
int rows = rowCol[0];
int cols = rowCol[1];
// **** ****
int[][] mat = new int[rows][];
// **** read values for rows ****
for (int r = 0; r < rows; r++) {
mat[r] = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
}
// **** close the buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< rows: " + rows + " cols: " + cols);
System.out.println("main <<< mat: ");
for (int r = 0; r < rows; r++)
System.out.println(Arrays.toString(mat[r]));
// **** diagonal sort matrix ****
mat = diagonalSort(mat);
// ???? ????
System.out.println("main <<< result: ");
for (int r = 0; r < rows; r++)
System.out.println(Arrays.toString(mat[r]));
}
The test scaffolding, which IS NOT PART OF THE SOLUTION, opens a buffered reader. We read and extract the values for the number of rows and columns in our matrix. We then create an empty matrix with the proper number of rows. In the loop we read the data for each row and populate the matrix. The buffered reader is closed. The information is displayed. This gives us an opportunity to check is all is well so far before passing the argument to the method we need to implement.
We then make a call to the method of interest and get back a sorted matrix. The matrix is then displayed. We can easily verify that the method is returning the proper values for the test cases.
/**
* Given an m x n matrix mat of integers,
* sort each matrix diagonal in ascending order
* and return the resulting matrix.
*
* Runtime: 7 ms, faster than 65.97% of Java online submissions.
* Memory Usage: 39.8 MB, less than 80.41% of Java online submissions.
*/
static int[][] diagonalSort1(int[][] mat) {
// **** sanity checks ****
if (mat.length == 1 || mat[0].length == 1)
return mat;
// **** initialization ****
int rows = mat.length;
int cols = mat[0].length;
List<Integer> lst = new ArrayList<Integer>();
// **** go up along the left side of the matrix ****
for (int rr = rows - 2; rr >= 0; rr--) {
// **** clear the list ****
lst.clear();
// **** go diagonally (copy to list) ****
for (int r = rr, c = 0; r < rows && c < cols; r++, c++) {
lst.add(mat[r]);
}
// **** sort the list ****
lst.sort((a,b) -> a - b);
// **** go diagonally (update matrix) ****
for (int r = rr, c = 0; r < rows && c < cols; r++, c++) {
mat[r] = lst.get(c);
}
}
// **** go right along the upper side of the matrix ****
for (int cc = 1; cc < cols - 1; cc++) {
// **** clear list ****
lst.clear();
// **** go diagonally (copy to list)****
for (int r = 0, c = cc; r < rows && c < cols; r++, c++) {
lst.add(mat[r]);
}
// **** sort the list ****
lst.sort((a,b) -> a - b);
// **** go diagonally (update matrix) ****
for (int r = 0, c = cc; r < rows && c < cols; r++, c++) {
mat[r] = lst.get(r);
}
}
// **** return diagonally sorted matrix ****
return mat;
}
Before we get into the code, let’s describe our approach. We will traverse the left column of our matrix from bottom to top. For each position in the left column, we will traverse it diagonally. When visiting the elements we will add them to a data structure. In this case an array list. After finishing the diagonal traversal, we will sort the elements in the data structure. We will then update the elements in the diagonal with the sorted values from the data structure.
We perform some sanity checks followed by an initialization section.
Note that we have two main loops. The first will be used to traverse the left column from bottom to top. The second to traverse the top row from left to right. Note that the first element which is in the left bottom corner and the top right element do not require sorting since they form a diagonal of one element. Also note that on the first loop we end with the diagonal that start at (0, 0) so the traversal of the top row needs to start at element (0, 1).
Note that we are traversing the matrix in a diagonal, so depending on the dimensions, we need to make sure we do not go past the bounding rows and columns.
In this version of the solution we use an array list. We need to clear the list for each diagonal we process. In the first diagonal pass we populate the list. We then sort the contents of the list. Finally we need to traverse the list while updating the contents of the diagonal elements in the matrix.
The second main loop is quite similar to the first. We are now processing the diagonals that start on the top of our matrix.
When done we return the matrix.
We could have cloned the matrix as part of the initialization. In general it is not desirable to alter the arguments because we could induce side effects. When solving these problems we do not need to be concerned with side effects, but in production they may create very stealth issues that may be hard to find.
/**
* Given an m x n matrix mat of integers,
* sort each matrix diagonal in ascending order
* and return the resulting matrix.
*
* Runtime: 5 ms, faster than 83.88% of Java online submissions.
* Memory Usage: 39.8 MB, less than 70.60% of Java online submissions.
*/
static int[][] diagonalSort(int[][] mat) {
// **** sanity checks ****
if (mat.length == 1 || mat[0].length == 1)
return mat;
// **** initialization ****
int rows = mat.length;
int cols = mat[0].length;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// **** go up along the left side of the matrix ****
for (int rr = rows - 2; rr >= 0; rr--) {
// **** go diagonally (copy to list) ****
for (int r = rr, c = 0; r < rows && c < cols; r++, c++) {
pq.add(mat[r]);
}
// **** go diagonally (update matrix) ****
for (int r = rr, c = 0; r < rows && c < cols; r++, c++) {
mat[r] = pq.remove();
}
}
// **** go right along the upper side of the matrix ****
for (int cc = 1; cc < cols - 1; cc++) {
// **** go diagonally (copy to list)****
for (int r = 0, c = cc; r < rows && c < cols; r++, c++) {
pq.add(mat[r]);
}
// **** go diagonally (update matrix) ****
for (int r = 0, c = cc; r < rows && c < cols; r++, c++) {
mat[r] = pq.remove();
}
}
// **** return diagonally sorted matrix ****
return mat;
}
This is quite similar than our previous approach. We use a priority queue to eliminate the sorting step that we required when using the array list. In addition in this approach we remove elements from the queue so there is no need to clear the elements in the priority queue between diagonals.
When done we return the result. Note that the comments regarding side effects hold true as well.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 6,401 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com