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

1. Initialize variables row and col as the number of rows and columns in the matrix, respectively.

2. 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].
3. 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.

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.