Print matrix in snake pattern from the last column
Given a matrix of 2-Dimensional array of n rows and n columns. Print this matrix in snake 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 1 4 5 6 9 8 7 Input: mat[][] = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 4 3 2 1 5 6 7 8 12 11 10 9 13 14 15 16
Algorithm:
- Start traversing from top right cell belonging to row 0 and column n-1.
- First move will always be a horizontal move towards LEFT(WEST) direction.
- Alternatively Horizontal and vertical moves are made during matrix traversal.
- In a single horizontal move, we traverse multiple cells till we reach any of the wall of the matrix.
- In a horizontal move, if the row is odd numbered, we move in RIGHT(EAST) direction else we move in LEFT(WEST) direction
- In a single vertical move, we traverse a single cell in DOWNWARDS direction.
Below is the implementation of the above algorithm:
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) { for ( int i = 0; i < n; i++) { if (i%2 == 1) for ( int j = 0; j < n; j++) printf ( "%d " , mat[i][j]); else for ( int j = n - 1; j >= 0; j--) printf ( "%d " , mat[i][j]); } } // 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) { for ( int i = 0 ; i < n; i++) { if (i % 2 == 1 ) { for ( int j = 0 ; j < n; j++) { System.out.print( Integer.toString(mat[i][j]) + " " ); } } else { for ( int j = n - 1 ; j >= 0 ; j--) { System.out.print( Integer.toString(mat[i][j]) + " " ); } } } } // 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 ); } } |
Python3
# Python3 program for traversing a matrix from column n-1 import sys; # Function used for traversing over the given matrix def traverseMatrix(mat, n): for i in range (n): if i & 1 : for j in range (n): print ( str (mat[i][j]) + " ", end = " ") else : for j in range (n - 1 , - 1 , - 1 ): print ( str (mat[i][j]) + " ", end = " ") # 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) |
C#
// CSHARP program for traversing a matrix from column n-1 using System; using System.Linq; class GFG { // Function used for traversing over the given matrix static void traverseMatrix( int [, ] mat, int n) { for ( int i = 0; i < n; i++) { if (i % 2 == 1) { for ( int j = 0; j < n; j++) { Console.Write(mat[i, j].ToString() + " " ); } } else { for ( int j = n - 1; j >= 0; j--) { Console.Write(mat[i, j].ToString() + " " ); } } } } // Driver function public static void Main() { // 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); } } |
PHP
<?php // PHP program for traversing a matrix from column n-1 # Function used for traversing over the given matrix function traverseMatrix( $mat , $n ){ for ( $i = 0; $i < $n ; $i ++) { if ( $i & 1) { for ( $j = 0; $j < $n ; $j ++) { print ( $mat [ $i ][ $j ]. " " ); } } else { for ( $j = $n - 1; $j >= 0; $j --) { print ( $mat [ $i ][ $j ]. " " ); } } } } // 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 ); ?> |
Javascript
<script> // Javascript program for traversing a matrix from column n-1 // Function used for traversing over the given matrix function traverseMatrix(mat, n) { for ( var i = 0; i < n; i++) { if (i % 2 == 1) { for ( var j = 0; j < n; j++) { document.write(mat[i][j] + " " ); } } else { for ( var j = n - 1; j >= 0; j--) { document.write(mat[i][j] + " " ); } } } } // number of rows and columns var n = 5; // 5x5 matrix var 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 shruti456rawal </script> |
Output
5 4 3 2 1 6 7 8 9 10 15 14 13 12 11 16 17 18 19 20 25 24 23 22 21
Complexity Analysis:
- Time Complexity: O(N^2)
- Space Complexity: O(1)