Print matrix in diagonal pattern
Last Updated :
11 Sep, 2023
Given a matrix of n*n size, the task is to print its elements in a diagonal pattern.
Input : mat[3][3] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}}
Output : 1 2 4 7 5 3 6 8 9.
Explanation: Start from 1
Then from upward to downward diagonally i.e. 2 and 4
Then from downward to upward diagonally i.e 7, 5, 3
Then from up to down diagonally i.e 6, 8
Then down to up i.e. end at 9.
Input : mat[4][4] = {{1, 2, 3, 10},
{4, 5, 6, 11},
{7, 8, 9, 12},
{13, 14, 15, 16}}
Output: 1 2 4 7 5 3 10 6 8 13 14 9 11 12 15 16 .
Explanation: Start from 1
Then from upward to downward diagonally i.e. 2 and 4
Then from downward to upward diagonally i.e 7, 5, 3
Then from upward to downward diagonally i.e. 10 6 8 13
Then from downward to upward diagonally i.e 14 9 11
Then from upward to downward diagonally i.e. 12 15
then end at 16
Approach: From the diagram it can be seen that every element is either printed diagonally upward or diagonally downward. Start from the index (0,0) and print the elements diagonally upward then change the direction, change the column and print diagonally downwards. This cycle continues until the last element is reached.
Algorithm:
- Create variables i=0, j=0 to store the current indices of row and column
- Run a loop from 0 to n*n, where n is side of the matrix.
- Use a flag isUp to decide whether the direction is upwards or downwards. Set isUp = true initially the direction is going upward.
- If isUp = 1 then start printing elements by incrementing column index and decrementing the row index.
- Similarly if isUp = 0, then decrement the column index and increment the row index.
- Move to the next column or row (next starting row and column
- Do this till all the elements get traversed.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
void printMatrixDiagonal(int mat[MAX][MAX], int n)
{
int i = 0, j = 0;
bool isUp = true;
for (int k = 0; k < n * n;) {
if (isUp) {
for (; i >= 0 && j < n; j++, i--) {
cout << mat[i][j] << " ";
k++;
}
if (i < 0 && j <= n - 1)
i = 0;
if (j == n)
i = i + 2, j--;
}
else {
for (; j >= 0 && i < n; i++, j--) {
cout << mat[i][j] << " ";
k++;
}
if (j < 0 && i <= n - 1)
j = 0;
if (i == n)
j = j + 2, i--;
}
isUp = !isUp;
}
}
int main()
{
int mat[MAX][MAX] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
int n = 3;
printMatrixDiagonal(mat, n);
return 0;
}
|
Java
import java.io.*;
class GFG {
static final int MAX = 100;
static void printMatrixDiagonal(int mat[][], int n)
{
int i = 0, j = 0;
boolean isUp = true;
for (int k = 0; k < n * n;) {
if (isUp) {
for (; i >= 0 && j < n; j++, i--) {
System.out.print(mat[i][j] + " ");
k++;
}
if (i < 0 && j <= n - 1)
i = 0;
if (j == n) {
i = i + 2;
j--;
}
}
else {
for (; j >= 0 && i < n; i++, j--) {
System.out.print(mat[i][j] + " ");
k++;
}
if (j < 0 && i <= n - 1)
j = 0;
if (i == n) {
j = j + 2;
i--;
}
}
isUp = !isUp;
}
}
public static void main(String[] args)
{
int mat[][] = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
int n = 3;
printMatrixDiagonal(mat, n);
}
}
|
Python 3
MAX = 100
def printMatrixDiagonal(mat, n):
i = 0
j = 0
k = 0
isUp = True
while k<n * n:
if isUp:
while i >= 0 and j<n :
print(str(mat[i][j]), end = " ")
k += 1
j += 1
i -= 1
if i < 0 and j <= n - 1:
i = 0
if j == n:
i = i + 2
j -= 1
else:
while j >= 0 and i<n :
print(mat[i][j], end = " ")
k += 1
i += 1
j -= 1
if j < 0 and i <= n - 1:
j = 0
if i == n:
j = j + 2
i -= 1
isUp = not isUp
if __name__ == "__main__":
mat = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9] ]
n = 3
printMatrixDiagonal(mat, n)
|
C#
using System;
class GFG {
static int MAX = 100;
static void printMatrixDiagonal(int[, ] mat, int n)
{
int i = 0, j = 0;
bool isUp = true;
for (int k = 0; k < n * n;) {
if (isUp) {
for (; i >= 0 && j < n; j++, i--) {
Console.Write(mat[i, j] + " ");
k++;
}
if (i < 0 && j <= n - 1)
i = 0;
if (j == n) {
i = i + 2;
j--;
}
}
else {
for (; j >= 0 && i < n; i++, j--) {
Console.Write(mat[i, j] + " ");
k++;
}
if (j < 0 && i <= n - 1)
j = 0;
if (i == n) {
j = j + 2;
i--;
}
}
isUp = !isUp;
}
}
public static void Main()
{
int[, ] mat = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
int n = 3;
printMatrixDiagonal(mat, n);
}
}
|
PHP
<?php
$MAX = 100;
function printMatrixDiagonal($mat, $n)
{
$i = 0;
$j = 0 ;
$isUp = true;
for ($k = 0;$k < $n * $n😉
{
if ($isUp)
{
for ( ;$i >= 0 && $j < $n;$j++, $i--)
{
echo $mat[$i][$j]." ";
$k++;
}
if ($i < 0 && $j <= $n - 1)
$i = 0;
if ($j == $n)
{
$i = $i + 2;
$j--;
}
}
else
{
for ( ; $j >= 0 &&
$i<$n ; $i++, $j--)
{
echo $mat[$i][$j]." ";
$k++;
}
if ($j < 0 && $i <= $n - 1)
$j = 0;
if ($i == $n)
{
$j = $j + 2;
$i--;
}
}
$isUp = !$isUp;
}
}
$mat= array(array(1, 2, 3),
array(4, 5, 6),
array(7, 8, 9));
$n = 3;
printMatrixDiagonal($mat, $n);
?>
|
Javascript
<script>
function printMatrixDiagonal(arr, len) {
let i = 0, j = 0;
let isUp = true;
for (let k = 0; k < len * len;) {
if (isUp) {
for (;i >= 0 && j < len; i--, j++) {
document.write(arr[i][j] + ' ');
k++;
}
if (i < 0 && j < len) i = 0;
if (j === len) i = i + 2, j--;
}
else {
for (;j >= 0 && i < len; i++, j--) {
document.write(arr[i][j] + ' ');
k++;
}
if (j < 0 && i < len) j = 0;
if (i === len) j = j + 2, i--;
}
isUp = !isUp
}
}
let arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
let arrLength = arr.length;
printMatrixDiagonal(arr, arrLength);
</script>
|
Output:
1 2 4 7 5 3 6 8 9
Complexity Analysis:
- Time Complexity: O(n*n).
To traverse the matrix O(n*n) time complexity is needed.
- Auxiliary Space: O(1).
As no extra space is required.
Alternate Implementation: This is another simple and compact implementation of the same approach as mentioned above.
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int mat[][4] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int n = 4, mode = 0, it = 0, lower = 0;
for (int t = 0; t < (2 * n - 1); t++) {
int t1 = t;
if (t1 >= n) {
mode++;
t1 = n - 1;
it--;
lower++;
}
else {
lower = 0;
it++;
}
for (int i = t1; i >= lower; i--) {
if ((t1 + mode) % 2 == 0) {
cout << (mat[i][t1 + lower - i]) << endl;
}
else {
cout << (mat[t1 + lower - i][i]) << endl;
}
}
}
return 0;
}
|
Java
import java.io.*;
public class MatrixDiag {
public static void main(String[] args)
{
int[][] mat = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int n = 4, mode = 0, it = 0, lower = 0;
for (int t = 0; t < (2 * n - 1); t++) {
int t1 = t;
if (t1 >= n) {
mode++;
t1 = n - 1;
it--;
lower++;
}
else {
lower = 0;
it++;
}
for (int i = t1; i >= lower; i--) {
if ((t1 + mode) % 2 == 0) {
System.out.println(mat[i][t1 + lower - i]);
}
else {
System.out.println(mat[t1 + lower - i][i]);
}
}
}
}
}
|
Python3
mat = [[ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ]];
n = 4
mode = 0
it = 0
lower = 0
for t in range(2 * n - 1):
t1 = t
if (t1 >= n):
mode += 1
t1 = n - 1
it -= 1
lower += 1
else:
lower = 0
it += 1
for i in range(t1, lower - 1, -1):
if ((t1 + mode) % 2 == 0):
print((mat[i][t1 + lower - i]))
else:
print(mat[t1 + lower - i][i])
|
C#
using System;
public class MatrixDiag {
public static void Main(String[] args)
{
int[, ] mat = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int n = 4, mode = 0, it = 0, lower = 0;
for (int t = 0; t < (2 * n - 1); t++) {
int t1 = t;
if (t1 >= n) {
mode++;
t1 = n - 1;
it--;
lower++;
}
else {
lower = 0;
it++;
}
for (int i = t1; i >= lower; i--) {
if ((t1 + mode) % 2 == 0) {
Console.WriteLine(mat[i, t1 + lower - i]);
}
else {
Console.WriteLine(mat[t1 + lower - i, i]);
}
}
}
}
}
|
Javascript
<script>
function MatrixDiag(arr){
let n = arr.length, mode = 0, it = 0, lower = 0;
for(let t=0; t< (2 * n - 1); t++){
let t1 = t;
if(t1 >= n){
mode++;
t1 = n - 1;
it--;
lower++;
} else {
lower = 0;
it++;
}
for(let i = t1; i>= lower; i--){
if((t1 + mode) % 2 === 0){
console.log(arr[i][t1 + lower - i])
} else{
console.log(arr[t1 + lower - i][i])
}
}
}
}
let arr = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
];
MatrixDiag(arr)
</script>
|
Output:
1
2
5
9
6
3
4
7
10
13
14
11
8
12
15
16
Time complexity: O(n2).
Auxiliary Space: O(1).
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...