Posted on by Kalkicode
Code Matrix

# Diagonal bottom up traversal of matrix in 45 degree

In this programming tutorial, we will explore the concept of diagonal traversal of a matrix at a 45-degree angle from the bottom to the top. We will walk you through the problem statement, provide a detailed explanation using a suitable example, present the algorithm, pseudocode, and implementation in C, discuss the output, and conclude with the time complexity analysis. ## Problem Statement

Given a matrix, we are tasked with traversing its elements diagonally from the bottom to the top at a 45-degree angle and printing those elements.

## Example

Consider the following matrix:

``````1   2   3   4   5
6   7   8   9  10
11 12  13  14  15
16 17  18  19  20``````

The expected output of the diagonal traversal is:
`1 6 2 11 7 3 16 12 8 4 17 13 9 5 18 14 10 19 15 20`

## Idea to Solve

The problem can be solved by dividing it into two parts: the first half diagonal elements and the second half diagonal elements. For the first half, we iterate through each row and traverse the diagonal in a bottom-up manner. For the second half, we start from the second column and iterate through the rows while traversing the diagonal elements.

## Algorithm

1. Initialize a matrix `arr` with the given elements.
2. For the first half diagonal elements:
• Loop through each row `i` from 0 to `ROW - 1`.
• Inside this loop, iterate through column `j` from 0 to `i` and ensure that `j < COL` and `i - j >= 0`.
• Print the element at `arr[i - j][j]`.
3. For the second half diagonal elements:
• Loop through each column `i` from 1 to `COL - 1`.
• Inside this loop, initialize `j` as `ROW - 1` and `k` as `i`.
• While `j >= 0` and `k < COL`, print the element at `arr[j][k]`, and decrement `j` and increment `k`.
4. End the program.

## Pseudocode

``````function diagonalTraversal(matrix):
for i from 0 to ROW - 1:
for j from 0 to i:
if j < COL and i - j >= 0:
print matrix[i - j][j]

for i from 1 to COL - 1:
j = ROW - 1
k = i
while j >= 0 and k < COL:
print matrix[j][k]
j = j - 1
k = k + 1``````

## Code Solution

``````/*
C Program
+ Diagonal traversal of matrix in 45 degree from bottom up
*/
#include<stdio.h>
#define ROW 4
#define COL 5
//Display element from bottom to top diagonal elements
void diagonal(int matrix[ROW][COL])
{
//First half elements
for (int i = 0; i < ROW; ++i)
{
for (int j = 0; j <=i && j < COL && i-j >=0; ++j)
{
printf("  %d",matrix[i-j][j] );
}
}

//Second half elements
for (int i = 1; i < COL; ++i)
{
for (int j = ROW-1 , k = i; j >= 0 && k < COL; --j, k++)
{

printf("  %d",matrix[j][k] );

}
}

}
int main(){

int arr[ROW][COL]= {
{1,  2,  3,  4,  5},
{6,  7,  8,  9,  10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20}
};

diagonal(arr);

return 0;
}```
```

#### Output

``  1  6  2  11  7  3  16  12  8  4  17  13  9  5  18  14  10  19  15  20``
``````/*
C++ Program
Diagonal traversal of matrix in 45 degree from bottom up
*/
#include<iostream>
#define ROW 4
#define COL 5
using namespace std;

class MyMatrix {
public:

//Display element from bottom to top diagonal elements
void diagonal(int matrix[ROW][COL])
{
//First half elements
for (int i = 0; i < ROW; ++i)
{
for (int j = 0; j <=i && j < COL && i-j >=0; ++j)
{
cout<<"  "<<matrix[i-j][j] ;
}
}

//Second half elements
for (int i = 1; i < COL; ++i)
{
for (int j = ROW-1 , k = i; j >= 0 && k < COL; --j, k++)
{
cout<<"  "<<matrix[j][k] ;
}
}

}
};
int main() {
MyMatrix obj;
int matrix[][COL] ={
{1,  2,  3,  4,  5},
{6,  7,  8,  9,  10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20}
};
obj.diagonal(matrix);

return 0;
}```
```

#### Output

``  1  6  2  11  7  3  16  12  8  4  17  13  9  5  18  14  10  19  15  20``
``````/*
Java Program
Diagonal traversal of matrix in 45 degree from bottom up
*/
public class MyMatrix {

//Display element from bottom to top diagonal elements
public void diagonal(int [][]matrix)
{
//Get the size of matrix
int row = matrix.length;
int col = matrix.length;

//First half elements
for (int i = 0; i < row; ++i)
{
for (int j = 0; j <=i && j < col && i-j >=0; ++j)
{
System.out.print("  "+matrix[i-j][j] );
}
}

//Second half elements
for (int i = 1; i < col; ++i)
{
for (int j = row-1 , k = i; j >= 0 && k < col; --j, k++)
{

System.out.print("  "+matrix[j][k] );

}
}

}
public static void main(String[] args) {
MyMatrix obj = new MyMatrix();
//Define matrix
int [][]matrix ={
{1,  2,  3,  4,  5},
{6,  7,  8,  9,  10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20}
};
obj.diagonal(matrix);

}
}```
```

#### Output

``  1  6  2  11  7  3  16  12  8  4  17  13  9  5  18  14  10  19  15  20``
``````/*
C# Program
Diagonal traversal of matrix in 45 degree from bottom up
*/
using System;
public class MyMatrix {

//Display element from bottom to top diagonal elements
public void diagonal(int[,] matrix) {
//Get the size of matrix
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);

//First half elements
for (int i = 0; i < row; ++i) {
for (int j = 0; j <= i && j < col && i - j >= 0; ++j) {
Console.Write("  " + matrix[i - j,j]);
}
}

//Second half elements
for (int i = 1; i < col; ++i) {
for (int j = row - 1, k = i; j >= 0 && k < col; --j, k++) {

Console.Write("  " + matrix[j,k]);

}
}

}
public static void Main(String[] args) {
MyMatrix obj = new MyMatrix();
//Define matrix
int[,] matrix = {
{
1,
2,
3,
4,
5
},
{
6,
7,
8,
9,
10
},
{
11,
12,
13,
14,
15
},
{
16,
17,
18,
19,
20
}
};
obj.diagonal(matrix);

}
}```
```

#### Output

``  1  6  2  11  7  3  16  12  8  4  17  13  9  5  18  14  10  19  15  20``
``````<?php
/*
Php Program
Diagonal traversal of matrix in 45 degree from bottom up
*/
class MyMatrix {
//Display element from bottom to top diagonal elements

public 	function diagonal(\$matrix) {
//Get the size of matrix
\$row = count(\$matrix);
\$col = count(\$matrix);
//First half elements

for (\$i = 0; \$i < \$row; ++\$i) {
for (\$j = 0; \$j <= \$i && \$j < \$col && \$i - \$j >= 0; ++\$j) {
echo(" ". \$matrix[\$i - \$j][\$j]);
}
}
//Second half elements

for (\$i = 1; \$i < \$col; ++\$i) {
for (\$j = \$row - 1, \$k = \$i; \$j >= 0 && \$k < \$col; --\$j, \$k++) {
echo(" ". \$matrix[\$j][\$k]);
}
}
}
};

function main() {
\$obj = new MyMatrix();
//Define matrix
\$matrix = array(array(1, 2, 3, 4, 5), array(6, 7, 8, 9, 10), array(11, 12, 13, 14, 15), array(16, 17, 18, 19, 20));
\$obj->diagonal(\$matrix);

}
main();```
```

#### Output

`` 1 6 2 11 7 3 16 12 8 4 17 13 9 5 18 14 10 19 15 20``
``````/*
Node Js Program
Diagonal traversal of matrix in 45 degree from bottom up
*/
class MyMatrix {
//Display element from bottom to top diagonal elements
diagonal(matrix) {
//Get the size of matrix
var row = matrix.length;
var col = matrix.length;
//First half elements

for (var i = 0; i < row; ++i) {
for (var j = 0; j <= i && j < col && i - j >= 0; ++j) {
process.stdout.write(" " + matrix[i - j][j]);
}
}

//Second half elements

for (var i = 1; i < col; ++i) {
for (var j = row - 1, k = i; j >= 0 && k < col; --j, k++) {
process.stdout.write(" " + matrix[j][k]);
}
}
}
}

function main(args) {
var obj = new MyMatrix();
//Define matrix
var matrix = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20]
];
obj.diagonal(matrix);

}
main();```
```

#### Output

`` 1 6 2 11 7 3 16 12 8 4 17 13 9 5 18 14 10 19 15 20``
``````# Python 3 Program
# Diagonal traversal of matrix in 45 degree from bottom up
class MyMatrix :
# Display element from bottom to top diagonal elements
def diagonal(self, matrix) :
row = len(matrix)
col = len(matrix)
# First half elements
i = 0
while (i < row) :
j = 0
while (j <= i and j < col and i - j >= 0) :
print(" ", matrix[i - j][j], end = "")
j += 1

i += 1

# Second half elements
i = 1
while (i < col) :
j = row - 1
k = i
while (j >= 0 and k < col) :
print(" ", matrix[j][k], end = "")
j -= 1
k += 1

i += 1

def main() :
obj = MyMatrix()
matrix = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20]
]
obj.diagonal(matrix)

if __name__ == "__main__":
main()```
```

#### Output

`` 1 6 2 11 7 3 16 12 8 4 17 13 9 5 18 14 10 19 15 20``
``````# Ruby Program
# Diagonal traversal of matrix in 45 degree from bottom up
class MyMatrix
# Display element from bottom to top diagonal elements
def diagonal(matrix)
row = matrix.length
col = matrix.length
# First half elements
i = 0
while (i < row)
j = 0
while (j <= i and j < col and i - j >= 0)
print(" ", matrix[i - j][j])
j += 1
end
i += 1
end
# Second half elements
i = 1
while (i < col)
j = row - 1
k = i
while (j >= 0 and k < col)
print(" ", matrix[j][k])
j -= 1
k += 1
end
i += 1
end
end
end
def main()
obj = MyMatrix.new()
matrix = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20]
]
obj.diagonal(matrix)
end
main()```
```

#### Output

`` 1 6 2 11 7 3 16 12 8 4 17 13 9 5 18 14 10 19 15 20``
``````/*
Scala Program
Diagonal traversal of matrix in 45 degree from bottom up
*/
class MyMatrix {
//Display element from bottom to top diagonal elements
def diagonal(matrix: Array[Array[Int]]): Unit = {
val row: Int = matrix.length;
val col: Int = matrix(0).length;

//First half elements
var i: Int = 0;
var j: Int = 0;
while (i < row) {
j = 0;
while (j <= i && j < col && i - j >= 0) {
print(" " + matrix(i - j)(j));
j += 1;
}
i += 1;
}
//Second half elements
i = 1;
while (i < col) {
j = row - 1;

var k: Int = i;
while (j >= 0 && k < col) {
print(" " + matrix(j)(k));
j -= 1;
k += 1;
}
i += 1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyMatrix = new MyMatrix();
val matrix: Array[Array[Int]] = Array(
Array(1, 2, 3, 4, 5),
Array(6, 7, 8, 9, 10),
Array(11, 12, 13, 14, 15),
Array(16, 17, 18, 19, 20));
obj.diagonal(matrix);
}
}```
```

#### Output

`` 1 6 2 11 7 3 16 12 8 4 17 13 9 5 18 14 10 19 15 20``
``````/*
Swift 4 Program
Diagonal traversal of matrix in 45 degree from bottom up
*/
class MyMatrix {
//Display element from bottom to top diagonal elements
func diagonal(_ matrix: [
[Int]
]) {
let row: Int = matrix.count;
let col: Int = matrix.count;
//First half elements
var i: Int = 0;
var j: Int = 0;
while (i < row) {
j = 0;
while (j <= i && j < col && i - j >= 0) {
print(" ", matrix[i - j][j], terminator: "");
j += 1;
}
i += 1;
}
//Second half elements
i = 1;
while (i < col) {
j = row - 1;
var k: Int = i;
while (j >= 0 && k < col) {
print(" ", matrix[j][k], terminator: "");
j -= 1;
k += 1;
}
i += 1;
}
}
}
func main() {
let obj: MyMatrix = MyMatrix();
let matrix: [
[Int]
] = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20]
];
obj.diagonal(matrix);
}
main();```
```

#### Output

``  1  6  2  11  7  3  16  12  8  4  17  13  9  5  18  14  10  19  15  20``

## Time Complexity Analysis

For the first half traversal, we have two nested loops: the outer loop runs `ROW` times, and the inner loop runs at most `COL` times. For the second half traversal, again we have two nested loops: the outer loop runs `COL - 1` times, and the inner loop runs at most `ROW` times. Therefore, the time complexity is dominated by the number of elements in the matrix, which is `ROW * COL`, resulting in O(ROW * COL) time complexity.

## Comment

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.

Categories
Relative Post