Diagonal Traversal of Matrix using DFS

I’ve encountered this problem in an Online Assessment(OA), the requirement was not exactly traversing diagonally, but I had to do something traversing diagonally.

Thinking about it during my OA hurt my brain, I had to think, after I put decent amount of thought into it, I was able to write a very messy code to do the job.

I wanted to give it another shot after the OA and ended up making it even messier but manageable, I wanted to use DFS as I was solving some questions related to Maze and paths in a maze.

Traversing Matrix diagonally

Above is the visual representation,
Now If we pick the first element 1 at (0,0) it has no valid neighbors diagonally
If we move onto element 2 at say i,j=(0,1) it as a valid neighbors at
(i+1, j-1) = (1,0)
For element 3 at i,j=(0,2), we have to move on until we find an invalid i,j by incrementing i (moving down) and decrementing j (moving left)
We would end up having (0,2)->(1,1) and (2,0)
We can add these to our stack until no valid neighbors and then print before popping them off.

With an objective to simplify it, I might’ve overdone it.

vector<vector<int>> matrix = {  

This is the same matrix in the above png.

vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));

Core DFS Logic ahead


5 2
9 6 3
13 10 7 4
14 11 8
15 12



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