Given a matrix of 2D array of n rows and m columns. Print this matrix in ZIG-ZAG fashion as shown in figure.
Example:
Input:
{{1, 2, 3}
{4, 5, 6}
{7, 8, 9}}
Output: 1 2 4 7 5 3 6 8 9Input : [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]]
Output:: 1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16
Try it on GfG Practice
This approach uses a diagonal traversal technique to print the matrix in a zig-zag pattern. It iterates through the matrix diagonally, switching between incrementing the row and column indices based on the current position. This creates a zig-zag path that covers all elements of the matrix.
Below is the implementation of the above approach:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Utility function to print matrix in zig-zag form
void zigZagMatrix(vector<vector<int>>& mat) {
int n = mat.size();
int m = mat[0].size();
int row = 0, col = 0;
// Boolean variable that is true if we need
// to increment 'row' value;
// otherwise, false if we increment 'col' value.
bool row_inc = 0;
// Print the first half of the zig-zag pattern
int mn = min(m, n);
for (int len = 1; len <= mn; ++len) {
for (int i = 0; i < len; ++i) {
cout << mat[row][col] << " ";
if (i + 1 == len) break;
// If row_inc is true, increment row
// and decrement col;
// otherwise, decrement row and increment col.
if (row_inc) ++row, --col;
else --row, ++col;
}
if (len == mn) break;
// Update row or col value based on the
// last increment
if (row_inc) ++row, row_inc = false;
else ++col, row_inc = true;
}
// Adjust row and col for the second half of the matrix
if (row == 0) {
if (col == m - 1) ++row;
else ++col;
row_inc = 1;
} else {
if (row == n - 1) ++col;
else ++row;
row_inc = 0;
}
// Print the second half of the zig-zag pattern
int MAX = max(m, n) - 1;
for (int len, diag = MAX; diag > 0; --diag) {
len = (diag > mn) ? mn : diag;
for (int i = 0; i < len; ++i) {
cout << mat[row][col] << " ";
if (i + 1 == len) break;
// Update row or col value based on the last increment
if (row_inc) ++row, --col;
else ++col, --row;
}
// Update row and col based on position in the matrix
if (row == 0 || col == m - 1) {
if (col == m - 1) ++row;
else ++col;
row_inc = true;
} else if (col == 0 || row == n - 1) {
if (row == n - 1) ++col;
else ++row;
row_inc = false;
}
}
}
// Driver code
int main() {
vector<vector<int>> mat = { { 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 } };
zigZagMatrix(mat);
return 0;
}
public class ZigZagMatrix {
// Utility function to print matrix in zig-zag form
public static void zigZagMatrix(int[][] mat) {
int n = mat.length;
int m = mat[0].length;
int row = 0, col = 0;
// Boolean variable that is true if we need to
// increment 'row' value;
// otherwise, false if we increment 'col' value.
boolean rowInc = false;
// Print the first half of the zig-zag pattern
int minDim = Math.min(m, n);
for (int len = 1; len <= minDim; ++len) {
for (int i = 0; i < len; ++i) {
System.out.print(mat[row][col] + " ");
if (i + 1 == len) break;
// If rowInc is true, increment row and decrement col;
// otherwise, decrement row and increment col.
if (rowInc) {
row++;
col--;
} else {
row--;
col++;
}
}
if (len == minDim) break;
// Update row or col value based on the last increment
if (rowInc) {
row++;
rowInc = false;
} else {
col++;
rowInc = true;
}
}
// Adjust row and col for the second half of the matrix
if (row == 0) {
if (col == m - 1) row++;
else col++;
rowInc = true;
} else {
if (row == n - 1) col++;
else row++;
rowInc = false;
}
// Print the second half of the zig-zag pattern
int maxDim = Math.max(m, n) - 1;
for (int len, diag = maxDim; diag > 0; --diag) {
len = (diag > minDim) ? minDim : diag;
for (int i = 0; i < len; ++i) {
System.out.print(mat[row][col] + " ");
if (i + 1 == len) break;
// Update row or col value based on the last increment
if (rowInc) {
row++;
col--;
} else {
col++;
row--;
}
}
// Update row and col based on position in the matrix
if (row == 0 || col == m - 1) {
if (col == m - 1) row++;
else col++;
rowInc = true;
} else if (col == 0 || row == n - 1) {
if (row == n - 1) col++;
else row++;
rowInc = false;
}
}
}
// Driver code
public static void main(String[] args) {
int[][] mat = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
zigZagMatrix(mat);
}
}
# Utility function to print matrix in zig-zag form
def zig_zag_matrix(mat):
n = len(mat)
m = len(mat[0])
row = 0
col = 0
# Boolean variable that is true if we need
# to increment 'row' value;
# otherwise, false if we increment 'col' value.
row_inc = False
# Print the first half of the zig-zag pattern
mn = min(m, n)
for length in range(1, mn + 1):
for i in range(length):
print(mat[row][col], end=' ')
if i + 1 == length:
break
# If row_inc is true, increment row
# and decrement col;
# otherwise, decrement row and increment col.
if row_inc:
row += 1
col -= 1
else:
row -= 1
col += 1
if length == mn:
break
# Update row or col value based on the
# last increment
if row_inc:
row += 1
row_inc = False
else:
col += 1
row_inc = True
# Adjust row and col for the second half of the matrix
if row == 0:
if col == m - 1:
row += 1
else:
col += 1
row_inc = True
else:
if row == n - 1:
col += 1
else:
row += 1
row_inc = False
# Print the second half of the zig-zag pattern
MAX = max(m, n) - 1
for diag in range(MAX, 0, -1):
length = mn if diag > mn else diag
for i in range(length):
print(mat[row][col], end=' ')
if i + 1 == length:
break
# Update row or col value based on the last increment
if row_inc:
row += 1
col -= 1
else:
col += 1
row -= 1
# Update row and col based on position in the matrix
if row == 0 or col == m - 1:
if col == m - 1:
row += 1
else:
col += 1
row_inc = True
elif col == 0 or row == n - 1:
if row == n - 1:
col += 1
else:
row += 1
row_inc = False
# Driver code
if __name__ == '__main__':
mat = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
zig_zag_matrix(mat)
using System;
using System.Collections.Generic;
class Program
{
static void ZigZagMatrix(int[,] mat)
{
int n = mat.GetLength(0);
int m = mat.GetLength(1);
int row = 0;
int col = 0;
// Boolean variable that is true if we need
// to increment 'row' value;
// otherwise, false if we increment 'col' value.
bool rowInc = false;
// Print the first half of the zig-zag pattern
int mn = Math.Min(m, n);
for (int length = 1; length <= mn; length++)
{
for (int i = 0; i < length; i++)
{
Console.Write(mat[row, col] + " ");
if (i + 1 == length)
break;
// If rowInc is true, increment row
// and decrement col;
// otherwise, decrement row and increment col.
if (rowInc)
{
row++;
col--;
}
else
{
row--;
col++;
}
}
if (length == mn)
break;
// Update row or col value based on the
// last increment
if (rowInc)
{
row++;
rowInc = false;
}
else
{
col++;
rowInc = true;
}
}
// Adjust row and col for the second half of the matrix
if (row == 0)
{
if (col == m - 1)
row++;
else
col++;
rowInc = true;
}
else
{
if (row == n - 1)
col++;
else
row++;
rowInc = false;
}
// Print the second half of the zig-zag pattern
int MAX = Math.Max(m, n) - 1;
for (int diag = MAX; diag > 0; diag--)
{
int length = (diag > mn) ? mn : diag;
for (int i = 0; i < length; i++)
{
Console.Write(mat[row, col] + " ");
if (i + 1 == length)
break;
// Update row or col value based on the last increment
if (rowInc)
{
row++;
col--;
}
else
{
col++;
row--;
}
}
// Update row and col based on position in the matrix
if (row == 0 || col == m - 1)
{
if (col == m - 1)
row++;
else
col++;
rowInc = true;
}
else if (col == 0 || row == n - 1)
{
if (row == n - 1)
col++;
else
row++;
rowInc = false;
}
}
}
// Driver code
static void Main()
{
int[,] mat = new int[,] {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 }
};
ZigZagMatrix(mat);
}
}
function zigZagMatrix(mat) {
const n = mat.length;
const m = mat[0].length;
let row = 0;
let col = 0;
// Boolean variable that is true if we need
// to increment 'row' value;
// otherwise, false if we increment 'col' value.
let rowInc = false;
// Print the first half of the zig-zag pattern
const mn = Math.min(m, n);
for (let length = 1; length <= mn; length++) {
for (let i = 0; i < length; i++) {
process.stdout.write(mat[row][col] + ' ');
if (i + 1 === length) break;
// If rowInc is true, increment row
// and decrement col;
// otherwise, decrement row and increment col.
if (rowInc) {
row++;
col--;
} else {
row--;
col++;
}
}
if (length === mn) break;
// Update row or col value based on the
// last increment
if (rowInc) {
row++;
rowInc = false;
} else {
col++;
rowInc = true;
}
}
// Adjust row and col for the second half of the matrix
if (row === 0) {
if (col === m - 1) row++;
else col++;
rowInc = true;
} else {
if (row === n - 1) col++;
else row++;
rowInc = false;
}
// Print the second half of the zig-zag pattern
const MAX = Math.max(m, n) - 1;
for (let diag = MAX; diag > 0; diag--) {
const length = diag > mn ? mn : diag;
for (let i = 0; i < length; i++) {
process.stdout.write(mat[row][col] + ' ');
if (i + 1 === length) break;
// Update row or col value based on the last increment
if (rowInc) {
row++;
col--;
} else {
col++;
row--;
}
}
// Update row and col based on position in the matrix
if (row === 0 || col === m - 1) {
if (col === m - 1) row++;
else col++;
rowInc = true;
} else if (col === 0 || row === n - 1) {
if (row === n - 1) col++;
else row++;
rowInc = false;
}
}
}
// Driver code
const mat = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
zigZagMatrix(mat);
Output
1 2 4 7 5 3 6 8 9
Time complexity: O(n*m)
Auxiliary space: O(1), since no extra space has been taken.