Diagonal traversal of a matrix
In various programming scenarios, we encounter the need to traverse and process elements of a matrix in a specific order. Diagonal traversal is a technique where we move along the diagonals of a matrix, visiting each element in a zigzag manner. This article delves into the diagonal traversal of a matrix, providing a comprehensive explanation, example, approach, algorithm, and code in Java, C++,Python etc. By the end, you'll have a clear understanding of how to diagonally traverse a matrix and extract its elements.

Problem Statement and Description
Given a matrix of dimensions M x N, we aim to traverse all its elements diagonally and print them in a specific order. Consider the matrix below as an example:
1 2 4 7 11
3 5 8 12 15
6 9 13 16 18
10 14 17 19 20
Our goal is to traverse this matrix diagonally and output the elements as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Idea to Solve the Problem
To achieve diagonal traversal, we need to observe the pattern in which we move through the matrix. We can notice that each diagonal can be uniquely identified by the sum of its row and column indices. Armed with this insight, we can divide the traversal into two halves: the first half where we iterate over the top half of the matrix (rows 0 to M-1), and the second half where we iterate over the bottom half of the matrix (columns 1 to N-1).
Algorithm
-
Initialize variables row and col as the number of rows and columns in the matrix, respectively.
-
First Half Diagonals
- Iterate i from 0 to col-1:
- Inside the loop, iterate j from i to 0 (inclusive) and while i -
j is less than row:
- Print the element at index data[i - j][j].
- Inside the loop, iterate j from i to 0 (inclusive) and while i -
j is less than row:
- Iterate i from 0 to col-1:
-
Second Half Diagonals
- Iterate i from 1 to row-1:
- Inside the loop, iterate j from col-1 to 0 (inclusive), and initialize
k as i.
- While j is greater than or equal to 0 and k is less than
row:
- Print the element at index data[k][j].
- Increment k.
- While j is greater than or equal to 0 and k is less than
row:
- Inside the loop, iterate j from col-1 to 0 (inclusive), and initialize
k as i.
- Iterate i from 1 to row-1:
Pseudocode
function diagonalView(matrix):
row = matrix.rows
col = matrix.columns
// First Half Diagonals
for i from 0 to col-1:
for j from i to 0:
if i - j < row:
print(matrix[i - j][j])
// Second Half Diagonals
for i from 1 to row-1:
k = i
for j from col-1 to 0:
if k < row:
print(matrix[k][j])
k = k + 1
-
1) Diagonal traversal of matrix in java
2) Diagonal traversal of matrix in c++
3) Diagonal traversal of matrix in c
4) Diagonal traversal of matrix in c#
5) Diagonal traversal of matrix in vb.net
6) Diagonal traversal of matrix in php
7) Diagonal traversal of matrix in node js
8) Diagonal traversal of matrix in python
9) Diagonal traversal of matrix in ruby
10) Diagonal traversal of matrix in scala
11) Diagonal traversal of matrix in swift
12) Diagonal traversal of matrix in kotlin
13) Diagonal traversal of matrix in golang
Time Complexity
The time complexity of this diagonal traversal algorithm is O(M x N), where M is the number of rows and N is the number of columns in the matrix. This is because in the worst case, we visit each element once while traversing the diagonals.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment