How to Solve Diagonal Traverse Algorithm in Java

This is my solution to problem 498 on Leet Code.

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,4,7,5,3,6,8,9]Explanation:

Note: The total number of elements of the given matrix will not exceed 10,000.

First, we check if the matrix is empty then return an empty array. This is our first edge case.

Next, we initialize the matrix variables. Matrices have rows and columns that are treated just like indices in an array. Our first variables are called row and column and are initialized to 0 (the first column and first row of our matrix). This will help us to pinpoint the exact index in our matrix.

Initialize variables that represent the column and row lengths. This will help us to traverse through the matrix.

Initialize a new array to store the matrix elements. We want the array to be big enough so we multiply the matrix row length by column length to find the right size for our new array.

Next, we create a for-loop to traverse through the new array so we can store the elements from our matrix.

At each iteration of the for-loop, the current array index will be set to the current matrix index. The current matrix index will be indicated by the row and column variables.

Now, for our first if-statement: if the sum of the current row and column index is even…..

If the current column is the last column, in the matrix, move to the next row.

If the the current row is the first row in the matrix, go to the next column.

Otherwise, go back a row and move to the next column.

If the sum of the current row and column index is not even, we can just write else. Inside our else statement….

If the current row is the last row in the matrix, move to the next column.

If the current column is the first column in the matrix, move to the next row.

Otherwise, go to the next row then go to the previous column.

Finally, we return the array.

Let’s see this in action on the example matrix from above.

First we check to see if the matrix is empty. The matrix has 9 integers, so it is not empty. Now we move to the next line where we initialize the variables for the rows and columns. Remember, row and column will indicate the specific index of the matrix. The length of each row and column will be indicated by the variables called mRow and mColumn.

Next, we start a for-loop to build our array.

The current index of the array is equal to the current matrix index. The current matrix index is indicated by the row and column variables. Both row and column were initialized to 0. The current index of the array is zero. So we change the integer at the first index of the array to the integer at the first column and row in the matrix, which is 1.

Next, we go through the matrix to determine the next integer to add the array. We check to see if the sum of the current row and column indices is even or odd. Both column and row are equal to 0. Zero is an even number.

We then check to see if the current column is the last column in the matrix. It is not. It is the first column. Is the current row the first row? Yes! So we move to the next column by an increment of 1.

Now, we go through the loop again. The current array index is 1.

The value of the value of the current array index is equal to the value of the current matrix index.

The currentIndex of the array is 1. We are at row[0] and column[1] in our matrix. Let’s change the value at array[1] from 0 to the value at matrix[0][1], which is 2.

Next, we check to see if the sum of the current row and column is even or odd.

The sum of the current row and column is 1. Since 1 is an odd number, we skip down to the else statement.

Now we check to see if the current row is the last row or if the current column is the is the first column. Since it is neither, we go to the the final else statement which says to go to the next row and previous column.

Back to the top, we set the current array index to the value at the current matrix index.

Because currentIndex equals 2, we are changing the value of the number in array[2]. To find this value, we go to the matrix at row 1, column 0. The value at matrix[1][0] is 4. Now we put the number 4 in array[2].

Again, we check to see if the sum of the current row and column are even or odd. The sum of row and column is 1, which is an odd number. Then we check to see if we are either at the last row or the first column in the matrix.

We aren’t at the last row, but we are at the first column. In this case, we go to the next row and stay in the same column.

Now we are at the 3rd index of the array. We are going to put whatever value that’s in the current matrix slot into array[3].

Lets go to row 2, column 0 in the matrix. There, we find the number 7. So 7 is what will go in array[3].

Again, we check to see if the sum of the current row and column is even or odd. The sum is 2 which is even. Then we check to see if we are either in the last column or first row.

Since we are in neither the first row nor the last column, we go back a row and move to the next column.

Back to the beginning of the for-loop. We are at the 4th index of the array. This means we change the value of array[4] to matrix[1][1]. The new value at array[4] is 5.

Next, we check to see if the sum of the current row and column is even or odd. The sum is even. Then we check to see if we are at either the last column or the first row. We are at neither so we go back one row and move forward one column.

At matrix[0][2], our current matrix index, we find the number 3. The number 3 will go into our current array index which is 5.

The sum of the current row and column is even. We are at the last column in the matrix. Now we move to the next row and stay in the same column.

The value at matrix[1][2] is 6. This will go into array[6].

The sum of the current row and column is odd. We are at neither the last row nor the first column in the matrix. So we go to the next row and the previous column.

The value at matrix[2][1] is 8, which will go into array[7].

The sum of the current row and column is odd. We are at the last row so we move to the next column and stay in the same row.

We are now at the final index. The value at matrix[2][2] is 9. The number 9 goes into array[8].

The sum of the current row and column is even. We are at the last column in the matrix. The row variable will increment by 1.

The program will go back to the beginning of the for-loop. The array is finished so we skip down to the line of code that calls for the return of the array.

Thanks for reading. Check out the source code on my github.

I’m raising $7k to for my college tuition. Please help by donating and/or sharing my gofundme.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store