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 matrix void 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 function int 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-1 class 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-1 using 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 matrix function 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 matrix def 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 function if __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 matrix function traverseMatrix(mat, n) { // Initial cell coordinates let cur_x = 0, cur_y = n - 1; // Variable used for keeping track of last move let prev_move = "" ; // Variable used for keeping count // of cells traversed till next move let 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 function function main() { // number of rows and columns let n = 5; // 5x5 matrix let 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(); |
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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!