Given a 2D mat of size n*n, print the matrix in the following pattern.
Examples:
Input: n = 2, mat[][] = [[1, 2],
[3, 4]]
Output: [1, 2, 3, 4]
Explanation:Input: n = 3, mat[][] = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Output: [1, 2, 4, 3, 5, 7, 6, 8, 9]
Explanation:
Try it on GfG Practice
Table of Content
[Naive Approach] Using Brute Force - O(n*n) Time and O(n*n) Space
The idea is to use the value of i + j, since elements with the same value lie on the same diagonal. We create a temporary array of arrays and store same diagonal elements at one place using (i+j) as index. Finally iterate over the temporary array to print the items diagonally.
#include <iostream>
#include <vector>
using namespace std;
void diagonalTraversal(vector<vector<int>> &mat) {
int n = mat.size();
vector<vector<int>> diag(2 * n - 1);
// Store diagonals
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
diag[i + j].push_back(mat[i][j]);
}
}
// Print result
for (int d = 0; d < 2 * n - 1; d++) {
for (int val : diag[d]) {
cout << val << " ";
}
}
}
int main() {
vector<vector<int>> mat = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
diagonalTraversal(mat);
return 0;
}
#include <stdio.h>
void diagonalTraversal(int n, int mat[n][n]) {
int total = 2 * n - 1;
int diag[total][n];
int size[total];
// Initialize sizes
for (int i = 0; i < total; i++) {
size[i] = 0;
}
// Store diagonals
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int d = i + j;
diag[d][size[d]] = mat[i][j];
size[d]++;
}
}
// Print result
for (int i = 0; i < total; i++) {
for (int j = 0; j < size[i]; j++) {
printf("%d ", diag[i][j]);
}
}
}
int main() {
int n = 3;
int mat[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
diagonalTraversal(n, mat);
return 0;
}
import java.util.ArrayList;
public class GFG {
static void diagonalTraversal(int[][] mat) {
int n = mat.length;
ArrayList<ArrayList<Integer>> diag = new ArrayList<>();
// Initialize lists
for (int i = 0; i < 2 * n - 1; i++) {
diag.add(new ArrayList<>());
}
// Store diagonals
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
diag.get(i + j).add(mat[i][j]);
}
}
// Print result
for (int d = 0; d < 2 * n - 1; d++) {
for (int val : diag.get(d)) {
System.out.print(val + " ");
}
}
}
public static void main(String[] args) {
int[][] mat = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
diagonalTraversal(mat);
}
}
def diagonalTraversal(mat):
n = len(mat)
diag = [[] for _ in range(2 * n - 1)]
# Store diagonals
for i in range(n):
for j in range(n):
diag[i + j].append(mat[i][j])
# Print result
for d in range(2 * n - 1):
for val in diag[d]:
print(val, end=" ")
if __name__ == "__main__":
mat = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
diagonalTraversal(mat)
using System;
using System.Collections.Generic;
class GFG {
static void DiagonalTraversal(int[,] mat, int n) {
List<List<int>> diag = new List<List<int>>();
// Initialize lists
for (int i = 0; i < 2 * n - 1; i++) {
diag.Add(new List<int>());
}
// Store diagonals
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
diag[i + j].Add(mat[i, j]);
}
}
// Print result
for (int d = 0; d < 2 * n - 1; d++) {
foreach (int val in diag[d]) {
Console.Write(val + " ");
}
}
}
static void Main() {
int[,] mat = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
DiagonalTraversal(mat, 3);
}
}
function diagonalTraversal(mat) {
let n = mat.length;
let diag = Array.from({ length: 2 * n - 1 }, () => []);
// Store diagonals
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
diag[i + j].push(mat[i][j]);
}
}
// Print result
for (let d = 0; d < 2 * n - 1; d++) {
for (let val of diag[d]) {
process.stdout.write(val + " ");
}
}
}
// Driver code
let mat = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
diagonalTraversal(mat);
Output
1 2 4 3 5 7 6 8 9
[Expected Approach] Using Direct Diagonal Traversal - O(n*n) Time and O(1) Space
Traverse each diagonal directly by starting from every element in the first row and then from every element in the last column (Except the first element of the last column). From each starting point, move diagonally (down-left) and print elements until going out of bounds.
- We first print diagonals beginning with first row elements (1, 2, 3 & 4)
- Then we print diagonals with the last column elements starting from 2nd (8, 12 & 16)
#include <iostream>
#include <vector>
using namespace std;
void diagonalTraversal(vector<vector<int>> &mat) {
int n = mat.size();
// Start from first row
for (int col = 0; col < n; col++) {
int i = 0, j = col;
while (i < n && j >= 0) {
cout << mat[i][j] << " ";
i++; j--;
}
}
// Start from last column (excluding first row)
for (int row = 1; row < n; row++) {
int i = row, j = n - 1;
while (i < n && j >= 0) {
cout << mat[i][j] << " ";
i++; j--;
}
}
}
int main() {
vector<vector<int>> mat = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
diagonalTraversal(mat);
return 0;
}
#include <stdio.h>
void diagonalTraversal(int n, int mat[n][n]) {
// Start from first row
for (int col = 0; col < n; col++) {
int i = 0, j = col;
while (i < n && j >= 0) {
printf("%d ", mat[i][j]);
i++; j--;
}
}
// Start from last column (excluding first row)
for (int row = 1; row < n; row++) {
int i = row, j = n - 1;
while (i < n && j >= 0) {
printf("%d ", mat[i][j]);
i++; j--;
}
}
}
int main() {
int n = 3;
int mat[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
diagonalTraversal(n, mat);
return 0;
}
public class GFG {
static void diagonalTraversal(int[][] mat) {
int n = mat.length;
// Start from first row
for (int col = 0; col < n; col++) {
int i = 0, j = col;
while (i < n && j >= 0) {
System.out.print(mat[i][j] + " ");
i++; j--;
}
}
// Start from last column (excluding first row)
for (int row = 1; row < n; row++) {
int i = row, j = n - 1;
while (i < n && j >= 0) {
System.out.print(mat[i][j] + " ");
i++; j--;
}
}
}
public static void main(String[] args) {
int[][] mat = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
diagonalTraversal(mat);
}
}
def diagonalTraversal(mat):
n = len(mat)
# Start from first row
for col in range(n):
i, j = 0, col
while i < n and j >= 0:
print(mat[i][j], end=" ")
i += 1
j -= 1
# Start from last column (excluding first row)
for row in range(1, n):
i, j = row, n - 1
while i < n and j >= 0:
print(mat[i][j], end=" ")
i += 1
j -= 1
if __name__ == "__main__":
mat = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
diagonalTraversal(mat)
using System;
class GFG {
static void DiagonalTraversal(int[,] mat, int n) {
// Start from first row
for (int col = 0; col < n; col++) {
int i = 0, j = col;
while (i < n && j >= 0) {
Console.Write(mat[i, j] + " ");
i++; j--;
}
}
// Start from last column (excluding first row)
for (int row = 1; row < n; row++) {
int i = row, j = n - 1;
while (i < n && j >= 0) {
Console.Write(mat[i, j] + " ");
i++; j--;
}
}
}
static void Main() {
int[,] mat = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
DiagonalTraversal(mat, 3);
}
}
function diagonalTraversal(mat) {
let n = mat.length;
// Start from first row
for (let col = 0; col < n; col++) {
let i = 0, j = col;
while (i < n && j >= 0) {
process.stdout.write(mat[i][j] + " ");
i++;
j--;
}
}
// Start from last column (excluding first row)
for (let row = 1; row < n; row++) {
let i = row, j = n - 1;
while (i < n && j >= 0) {
process.stdout.write(mat[i][j] + " ");
i++;
j--;
}
}
}
// Driver code
let mat = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
diagonalTraversal(mat);
Output
1 2 4 3 5 7 6 8 9