Given a matrix of 2-Dimensional array of n rows and n columns. Print this matrix in ZIG-ZAG fashion starting from column n-1 as shown in the figure below.
Examples:
Input: mat[][] = 1 2 3 4 5 6 7 8 9 Output: 3 2 6 9 5 1 4 8 7 Input: mat[][] = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 4 3 8 12 7 2 1 6 11 16 15 10 5 9 14 13
Algorithm:
- Start traversing from top right cell belonging to row 0 and column n-1.
- First move will always be towards LEFT(WEST) direction.
- We make a horizontal/vertical move in case the move is odd numbered.
- If the last move was in NORTH-WEST direction, move LEFT if there is no wall move towards LEFT, move DOWN in case there is a wall on the LEFT.
- If the last move was in SOUTH-EAST direction, move DOWN if there is no wall DOWNWARDS, move LEFT in case there is a wall DOWNWARDS.
- We make a diagonal move in case the move is even numbered.
- We choose to move towards SOUTH-EAST and NORTH-WEST directions alternatively starting with SOUTH-EAST move.
- In a single diagonal move we keep traversing multiple cells in the same direction until we reach any of the walls of the matrix. Pseudocode:
if ((move_cnt >> 1) & 1) {
// move south east
}
else {
// move north west
}
Variables Used
- mat: Given NxN matrix
- cur_x: Current row number
- cur_y: Current column number
- prev_move: Used to keep track of previous move
- move_cnt: Used to keep track of number of moves made
- cell_cnt: Used to keep track of number of cells traversed
Implementation:
C++
// C++ program for traversing a matrix from column n-1#include <bits/stdc++.h>using namespace std;// Function used for traversing over the given matrixvoid traverseMatrix(vector<vector<int> > mat, int n){ // Initial cell coordinates int cur_x = 0, cur_y = n - 1; // Variable used for keeping track of last move string prev_move = ""; // Variable used for keeping count // of cells traversed till next move int move_cnt = 1; int cell_cnt = 1; printf("%d ", mat[cur_x][cur_y]); while (cell_cnt < n * n) { // odd numbered move [SINGLE VERTICAL/HORIZONTAL] if (move_cnt & 1) { // last move was made in north east direction if (prev_move == "NORTH_WEST" or prev_move == "") { // move left if (cur_y != 0) { --cur_y; prev_move = "LEFT"; } // move down else { ++cur_x; prev_move = "DOWN"; } } // last move was made in south east direction else { // move down if (cur_x != n - 1) { ++cur_x; prev_move = "DOWN"; } // move left else { --cur_y; prev_move = "LEFT"; } } printf("%d ", mat[cur_x][cur_y]); ++cell_cnt; } // even numbered move/s [DIAGONAL/S] else { if ((move_cnt >> 1) & 1) { // move south east while (cur_x < n - 1 and cur_y < n - 1) { ++cur_x; ++cur_y; prev_move = "SOUTH_EAST"; printf("%d ", mat[cur_x][cur_y]); ++cell_cnt; } } else { // move north west while (cur_x > 0 and cur_y > 0) { --cur_x; --cur_y; prev_move = "NORTH_WEST"; printf("%d ", mat[cur_x][cur_y]); ++cell_cnt; } } } ++move_cnt; }}// Driver functionint main(){ // number of rows and columns int n = 5; // 5x5 matrix vector<vector<int> > mat{ { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, { 21, 22, 23, 24, 25 } }; traverseMatrix(mat, n); return 0;} |
Java
// Java program for traversing a matrix from column n-1class GFG { // Function used for traversing over the given matrix static void traverseMatrix(int[][] mat, int n) { // Initial cell coordinates int cur_x = 0, cur_y = n - 1; // Variable used for keeping track of last move String prev_move = ""; // Variable used for keeping count // of cells traversed till next move int move_cnt = 1; int cell_cnt = 1; System.out.print(Integer.toString( mat[cur_x][cur_y]) + " "); while (cell_cnt < n * n) { // odd numbered move // [SINGLE VERTICAL/HORIZONTAL] if (move_cnt % 2 == 1) { // last move was made in north east direction if (prev_move == "NORTH_WEST" || prev_move == "") { // move left if (cur_y != 0) { --cur_y; prev_move = "LEFT"; } // move down else { ++cur_x; prev_move = "DOWN"; } } // last move was made in south east direction else { // move down if (cur_x != n - 1) { ++cur_x; prev_move = "DOWN"; } // move left else { --cur_y; prev_move = "LEFT"; } } System.out.print(Integer.toString( mat[cur_x][cur_y]) + " "); ++cell_cnt; } // even numbered move/s [DIAGONAL/S] else { if ((move_cnt >> 1) % 2 == 1) { // move south east while (cur_x < n - 1 && cur_y < n - 1) { ++cur_x; ++cur_y; prev_move = "SOUTH_EAST"; System.out.print( Integer.toString( mat[cur_x][cur_y]) + " "); ++cell_cnt; } } else { // move north west while (cur_x > 0 && cur_y > 0) { --cur_x; --cur_y; prev_move = "NORTH_WEST"; System.out.print( Integer.toString( mat[cur_x][cur_y]) + " "); ++cell_cnt; } } } ++move_cnt; } } // Driver function public static void main(String[] args) { // number of rows and columns int n = 5; // 5x5 matrix int[][] mat = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, { 21, 22, 23, 24, 25 } }; traverseMatrix(mat, n); System.exit(0); }} |
C#
// C# program for traversing a matrix from column n-1using System;using System.Collections.Generic;class GFG { // Function used for traversing over the given matrix public static void traverseMatrix(int[,] mat, int n) { // Initial cell coordinates int cur_x = 0, cur_y = n - 1; // Variable used for keeping track of last move string prev_move = ""; // Variable used for keeping count // of cells traversed till next move int move_cnt = 1; int cell_cnt = 1; Console.Write(mat[cur_x,cur_y].ToString() + " "); while (cell_cnt < n * n) { // odd numbered move // [SINGLE VERTICAL/HORIZONTAL] if (move_cnt % 2 == 1) { // last move was made in north east // direction if (prev_move == "NORTH_WEST" || prev_move == "") { // move left if (cur_y != 0) { --cur_y; prev_move = "LEFT"; } // move down else { ++cur_x; prev_move = "DOWN"; } } // last move was made in south east // direction else { // move down if (cur_x != n - 1) { ++cur_x; prev_move = "DOWN"; } // move left else { --cur_y; prev_move = "LEFT"; } } Console.Write(mat[cur_x,cur_y].ToString() + " "); ++cell_cnt; } // even numbered move/s [DIAGONAL/S] else { if ((move_cnt >> 1) % 2 == 1) { // move south east while (cur_x < n - 1 && cur_y < n - 1) { ++cur_x; ++cur_y; prev_move = "SOUTH_EAST"; Console.Write( mat[cur_x,cur_y].ToString() + " "); ++cell_cnt; } } else { // move north west while (cur_x > 0 && cur_y > 0) { --cur_x; --cur_y; prev_move = "NORTH_WEST"; Console.Write( mat[cur_x,cur_y].ToString() + " "); ++cell_cnt; } } } ++move_cnt; } } // Driver function public static void Main(String[] args) { // number of rows and columns int n = 5; // 5x5 matrix int[, ] mat = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 }, { 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 }, { 21, 22, 23, 24, 25 } }; traverseMatrix(mat, n); }}// This code is contributed by Abhijeet Kumar(abhijeet19403) |
PHP
<?php// PHP program for traversing a matrix from column n-1// Function used for traversing over the given matrixfunction traverseMatrix($mat, $n){ # Initial cell coordinates $cur_x = 0; $cur_y = $n - 1; # Variable used for keeping track of last move $prev_move = ""; # Variable used for keeping count # of cells traversed till next move $move_cnt = 1; $cell_cnt = 1; print($mat[$cur_x][$cur_y]." "); while ($cell_cnt < $n * $n) { # odd numbered move [SINGLE VERTICAL/HORIZONTAL] if ($move_cnt & 1) { # last move was made in north east direction if ($prev_move == "NORTH_WEST" or $prev_move == "") { # move left if ($cur_y != 0){ $cur_y -= 1; $prev_move = "LEFT"; } # move down else { $cur_x += 1; $prev_move = "DOWN"; } } # last move was made in south east direction else { # move down if($cur_x != $n - 1){ $cur_x += 1; $prev_move = "DOWN"; } # move left else { $cur_y -= 1; $prev_move = "LEFT"; } } print($mat[$cur_x][$cur_y]." "); $cell_cnt += 1; } # even numbered move/s [DIAGONAL/S] else { if (($move_cnt >> 1) & 1) { # move south east while ($cur_x < $n - 1 and $cur_y < $n - 1) { $cur_x += 1; $cur_y += 1; $prev_move = "SOUTH_EAST"; print($mat[$cur_x][$cur_y]." "); $cell_cnt += 1; } } else { # move north west while($cur_x > 0 and $cur_y > 0) { $cur_x -=1 ; $cur_y -= 1; $prev_move = "NORTH_WEST"; print($mat[$cur_x][$cur_y]." "); $cell_cnt += 1; } } } $move_cnt += 1; }} // Driver function# number of rows and columns$n = 5;# 5x5 matrix$mat = 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), array(21, 22, 23, 24, 25));traverseMatrix($mat, $n);?> |
Python3
# Function used for traversing over the given matrixdef traverseMatrix(mat, n): # Initial cell coordinates cur_x = 0 cur_y = n - 1 # Variable used for keeping track of last move prev_move = "" # Variable used for keeping count # of cells traversed till next move move_cnt = 1 cell_cnt = 1 print(mat[cur_x][cur_y], end=" ") while (cell_cnt < n * n): # odd numbered move [SINGLE VERTICAL/HORIZONTAL] if (move_cnt & 1): # last move was made in north east direction if (prev_move == "NORTH_WEST" or prev_move == ""): # move left if (cur_y != 0): cur_y -= 1 prev_move = "LEFT" # move down else: cur_x += 1 prev_move = "DOWN" # last move was made in south east direction else: # move down if (cur_x != n - 1): cur_x += 1 prev_move = "DOWN" # move left else: cur_y -= 1 prev_move = "LEFT" print(mat[cur_x][cur_y], end=" ") cell_cnt += 1 # even numbered move/s [DIAGONAL/S] else: if ((move_cnt >> 1) & 1): # move south east while (cur_x < n - 1 and cur_y < n - 1): cur_x += 1 cur_y += 1 prev_move = "SOUTH_EAST" print(mat[cur_x][cur_y], end=" ") cell_cnt += 1 else: # move north west while (cur_x > 0 and cur_y > 0): cur_x -= 1 cur_y -= 1 prev_move = "NORTH_WEST" print(mat[cur_x][cur_y], end=" ") cell_cnt += 1 move_cnt += 1# Driver functionif __name__ == "__main__": # number of rows and columns n = 5 # 5x5 matrix mat = [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]] traverseMatrix(mat, n) |
Javascript
// JavaScript program for traversing a matrix from column n-1// Function used for traversing over the given matrixfunction traverseMatrix(mat, n){// Initial cell coordinateslet cur_x = 0, cur_y = n - 1;// Variable used for keeping track of last movelet prev_move = "";// Variable used for keeping count// of cells traversed till next movelet move_cnt = 1;let cell_cnt = 1;console.log(mat[cur_x][cur_y]);while (cell_cnt < n * n) { // odd numbered move // [SINGLE VERTICAL/HORIZONTAL] if (move_cnt % 2 === 1) { // last move was made in north east direction if (prev_move == "NORTH_WEST" || prev_move === "") { // move left if (cur_y !== 0) { --cur_y; prev_move = "LEFT"; } // move down else { ++cur_x; prev_move = "DOWN"; } } // last move was made in south east direction else { // move down if (cur_x !== n - 1) { ++cur_x; prev_move = "DOWN"; } // move left else { --cur_y; prev_move = "LEFT"; } } console.log(mat[cur_x][cur_y]); ++cell_cnt; } // even numbered move/s [DIAGONAL/S] else { if ((move_cnt >> 1) % 2 === 1) { // move south east while (cur_x < n - 1 && cur_y < n - 1) { ++cur_x; ++cur_y; prev_move = "SOUTH_EAST"; console.log(mat[cur_x][cur_y]); ++cell_cnt; } } else { // move north west while (cur_x > 0 && cur_y > 0) { --cur_x; --cur_y; prev_move = "NORTH_WEST"; console.log(mat[cur_x][cur_y]); ++cell_cnt; } } } ++move_cnt;}}// Driver functionfunction main(){// number of rows and columnslet n = 5;// 5x5 matrixlet mat = [ [ 1, 2, 3, 4, 5 ], [ 6, 7, 8, 9, 10 ], [ 11, 12, 13, 14, 15 ], [ 16, 17, 18, 19, 20 ], [ 21, 22, 23, 24, 25 ]];traverseMatrix(mat, n);}main(); |
Output
5 4 10 15 9 3 2 8 14 20 25 19 13 7 1 6 12 18 24 23 17 11 16 22 21
Complexity Analysis:
- Time Complexity: O(N^2)
- Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
