Print matrix in zig-zag fashion from the last column

0 0 9 minutes read

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();

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 zambiatek!