Question: Print Matrix diagonally
###Problem Given a 2D matrix, print all elements of the given matrix in diagonal order.
There are 3 diagonal orders that we may want to consider.
-
Row oriented order:
-
Col oriented order:
NOTE: this is just a “flipped” version of case 1 -
Zig Zag:
NOTE: Assuming we can solve the first 2 cases, this case is just swapping between them
###Approach I always thought this question was more about tracking indexes carefully, remembering when to increment indexes as we run out of rows to print and have to move forward on columns (and using flags to remember direction in the zig zag case). I recently came across a solution where all of that goes away!
The idea is simple. We need to think in terms of traversing an “inflated” matrix in the row diagonal / column diagonal / zig zag pattern. The “inflated” matrix looks like:
And here’s how to traverse this matrix (making the traversal code just 4 lines!):
This means we’ll never run out of rows before we’re done all entries from the base matrix. Meaning, we can just use a single check and traversal pattern to scan through all entries.
We won’t be building this matrix in memory, but the way we traverse our input matrix is going to be based on this “inflated” matrix. For everyone wondering what happens to indexes on this “inflated” matrix, that don’t exist in the original base matrix .. we simply skip them!
###Code
======================================================================