Zigzag traversal of matrix

Zigzag is another way of to traverse diagonal elements of a given matrix. Let see an example to understand this problem.

Zigzag traversal of matrix

Here given code implementation process.

/*
  C Program 
+ Zigzag traversal of Matrix
*/
#include<stdio.h>
#define ROW 5
#define COL 4



void reverse(int data[ROW][COL],int i ,int j,int k)
{
  if(j >= 0 && k < COL)
  {
    reverse(data,i ,j-1,k+1);
    printf("  %d",data[j][k] );
  }
}
void zigzag(int data[ROW][COL])
{
  int counter=0;
  //First Half Elements
  for (int i = 0; i < ROW; ++i,counter++)
  {
    if(counter%2==0)
    {
      for (int j = 0; j <=i && j < COL && i-j >=0; ++j)
      {
        
        printf("  %d",data[i-j][j] );
        
      }
    }
    else
    {

      for (int j = i,k=0;  j >=0  && j < COL && k <=i; --j,++k)
      {
        
        printf("  %d",data[k][j] );
        
      }
    }


  }
  
  //Second Half
  for (int i = 1; i < COL; ++i,counter++)
  {
    if(counter%2==0)
    {
      for (int j = ROW-1 , k = i; j >= 0 && k < COL; --j, k++)
      {
        
        printf("  %d",data[j][k] );
        
      }
    }
    else
    {
      reverse(data,i ,ROW-1,i);
    }
  }
  
 
}
int main(){

  int arr[ROW][COL]= {
    {1,  2,  3,  4},
    {6,  7,  8,  9}, 
    {11, 12, 13, 14},
    {16, 17, 18, 19},
    {1,   2,  3,  4}
  };

  zigzag(arr);

  return 0;
}

Output

  1  2  6  11  7  3  4  8  12  16  1  17  13  9  14  18  2  3  19  4
/*
 C++ Program
 Zigzag traversal of Matrix
*/

#include<iostream>
#define ROW 5
#define COL 4
using namespace std;

class Matrix {
  public:
    int row;
  int col;
  Matrix() {
    this->row = ROW;
    this->col = COL;
  }
  void reverse(int data[ROW][COL], int i, int j, int k) {
    if (j >= 0 && k < this->col) {
      this->reverse(data, i, j - 1, k + 1);
      cout << "  " << data[j][k];
    }
  }
  void zigzag(int data[ROW][COL]) {
    int counter = 0;
    int i = 0, j = 0, k = 0;
    while (i < this->row) {
      if (counter % 2 == 0) {
        j = 0;
        while (j <= i && j < this->col && i - j >= 0) {
          cout << "  " << data[i - j][j];
          j++;
        }
      } else {
        j = i;
        k = 0;
        while (j >= 0 && j < this->col && k <= i) {
          cout << "  " << data[k][j];
          j--;
          k++;
        }
      }
      i++;
      counter++;
    }
    i = 1;
    while (i < this->col) {
      if (counter % 2 == 0) {
        j = this->row - 1;
        k = i;
        while (j >= 0 && k < this->col) {
          cout << "  " << data[j][k];
          j--;
          k++;
        }
      } else {
        this->reverse(data, i, this->row - 1, i);
      }
      counter++;
      i++;
    }
  }
};
int main() {
  int arr[ROW][COL] = {
    {
      1,
      2,
      3,
      4
    },
    {
      6,
      7,
      8,
      9
    },
    {
      11,
      12,
      13,
      14
    },
    {
      16,
      17,
      18,
      19
    },
    {
      1,
      2,
      3,
      4
    }
  };
  Matrix obj;
  obj.zigzag(arr);
  return 0;
}

Output

  1  2  6  11  7  3  4  8  12  16  1  17  13  9  14  18  2  3  19  4
/*
  Java Program 
+ Zigzag traversal of Matrix
*/
public class Matrix {
  
  public int row;
  public int col;

  public Matrix(int[][] arr) {
    //get length of row and cols
    row = arr.length;
    col = arr[0].length;
  }
  public void reverse(int[][] data, int i, int j, int k) {

    if (j >= 0 && k < col) {
      reverse(data, i, j - 1, k + 1);

      System.out.print("  "+ data[j][k]);
    }
  }
  public void zigzag(int[][] data) {
    int counter = 0 ;
  

    int i = 0, j = 0, k = 0;
    while (i < row) {

      if (counter % 2 == 0) {
        j = 0;
        while (j <= i && j < col && i - j >= 0) {

          System.out.print("  "+ data[i - j][j]);
          j++;
        }
      } else {

        j = i;
        k = 0;
        while (j >= 0 && j < col && k <= i) {

          System.out.print("  "+ data[k][j]);
          j--;
          k++;
        }
      }

      i++;
      counter++;
    }
    i = 1;
    while (i < col) {

      if (counter % 2 == 0) {
        j = row - 1;
        k = i;
        while (j >= 0 && k < col) {

          System.out.print("  "+ data[j][k]);
          j--;
          k++;
        }
      } else {
        reverse(data, i, row - 1, i);
      }
      counter++;
      i++;
    }
  }

  public static void main(String[] args) {

    int[][] arr = {
        {1,  2,  3,  4},
        {6,  7,  8,  9}, 
        {11, 12, 13, 14},
        {16, 17, 18, 19},
        {1,   2,  3,  4}
      };

    Matrix obj = new Matrix(arr);

    obj.zigzag(arr);

  }
}

Output

  1  2  6  11  7  3  4  8  12  16  1  17  13  9  14  18  2  3  19  4
/*
  C# Program 
+ Zigzag traversal of Matrix
*/
using System;
public class Matrix {

	public int row;
	public int col;

	public Matrix(int[,] arr) {
		//get.Length of row and cols
		row = arr.GetLength(0);
		col = arr.GetLength(1);
	}
	public void reverse(int[,] data, int i, int j, int k) {

		if (j >= 0 && k < col) {
			reverse(data, i, j - 1, k + 1);

			Console.Write("  "+ data[j,k]);
		}
	}
	public void zigzag(int[,] data) {
		int counter = 0 ;


		int i = 0, j = 0, k = 0;
		while (i < row) {

			if (counter % 2 == 0) {
				j = 0;
				while (j <= i && j < col && i - j >= 0) {

					Console.Write("  "+ data[i - j,j]);
					j++;
				}
			} else {

				j = i;
				k = 0;
				while (j >= 0 && j < col && k <= i) {

					Console.Write("  "+ data[k,j]);
					j--;
					k++;
				}
			}

			i++;
			counter++;
		}
		i = 1;
		while (i < col) {

			if (counter % 2 == 0) {
				j = row - 1;
				k = i;
				while (j >= 0 && k < col) {

					Console.Write("  "+ data[j,k]);
					j--;
					k++;
				}
			} else {
				reverse(data, i, row - 1, i);
			}
			counter++;
			i++;
		}
	}

	public static void Main(String[] args) {

		int[,] arr = {
			{1,  2,  3,  4},
			{6,  7,  8,  9}, 
			{11, 12, 13, 14},
			{16, 17, 18, 19},
			{1,   2,  3,  4}
		};

		Matrix obj = new Matrix(arr);

		obj.zigzag(arr);

	}
}

Output

  1  2  6  11  7  3  4  8  12  16  1  17  13  9  14  18  2  3  19  4
# Python 3 Program
# Zigzag traversal of Matrix

class Matrix :

  def __init__(self, arr) :
    self.row = len(arr)
    self.col = len(arr[0])
  
  def reverse(self, data, i, j, k) :
    if (j >= 0 and k < self.col) :
      self.reverse(data, i, j - 1, k + 1)
      print(" ", data[j][k],end="")
    
  
  def zigzag(self, data) :
    counter = 0
    i = 0
    j = 0
    k = 0
    while (i < self.row) :
      if (counter % 2 == 0) :
        j = 0
        while (j <= i and j < self.col and i - j >= 0) :
          print(" ", data[i - j][j],end="")
          j += 1
        
      else :
        j = i
        k = 0
        while (j >= 0 and j < self.col and k <= i) :
          print(" ", data[k][j],end="")
          j -= 1
          k += 1
        
      
      i += 1
      counter += 1
    
    i = 1
    while (i < self.col) :
      if (counter % 2 == 0) :
        j = self.row - 1
        k = i
        while (j >= 0 and k < self.col) :
          print(" ", data[j][k],end="")
          j -= 1
          k += 1
        
      else :
        self.reverse(data, i, self.row - 1, i)
      
      counter += 1
      i += 1
    
  

def main() :
  arr = [
    [1, 2, 3, 4],
    [6, 7, 8, 9],
    [11, 12, 13, 14],
    [16, 17, 18, 19],
    [1, 2, 3, 4]
  ]
  obj = Matrix(arr)
  obj.zigzag(arr)

if __name__ == "__main__":
  main()

Output

  1  2  6  11  7  3  4  8  12  16  1  17  13  9  14  18  2  3  19  4
# Ruby Program
# Zigzag traversal of Matrix

class Matrix 
	attr_reader :row, :col
	attr_accessor :row, :col

	def initialize(arr) 
		@row = arr.length
		@col = arr[0].length
	end
	def reverse(data, i, j, k) 
		if (j >= 0 and k < @col) 
			self.reverse(data, i, j - 1, k + 1)
			print("  ", data[j][k])
		end
	end
	def zigzag(data) 
		counter = 0
		i = 0
		j = 0
		k = 0
		while (i < @row) 
			if (counter % 2 == 0) 
				j = 0
				while (j <= i and j < @col and i - j >= 0) 
					print("  ", data[i - j][j])
					j += 1
				end
			else 
				j = i
				k = 0
				while (j >= 0 and j < @col and k <= i) 
					print("  ", data[k][j])
					j -= 1
					k += 1
				end
			end
			i += 1
			counter += 1
		end
		i = 1
		while (i < @col) 
			if (counter % 2 == 0) 
				j = @row - 1
				k = i
				while (j >= 0 and k < @col) 
					print("  ", data[j][k])
					j -= 1
					k += 1
				end
			else 
				self.reverse(data, i, @row - 1, i)
			end
			counter += 1
			i += 1
		end
	end
end
def main() 
	arr = [
		[1, 2, 3, 4],
		[6, 7, 8, 9],
		[11, 12, 13, 14],
		[16, 17, 18, 19],
		[1, 2, 3, 4]
	]
	obj = Matrix.new(arr)
	obj.zigzag(arr)
end

main()

Output

  1  2  6  11  7  3  4  8  12  16  1  17  13  9  14  18  2  3  19  4
<?php

/*
 Php Program
 Zigzag traversal of Matrix
*/

class Matrix {
  public $row;
  public $col;

  function __construct($arr) {
    $this->row = count($arr);
    $this->col = count($arr[0]);
  }
  public  function reverse($data, $i, $j, $k) {
    if ($j >= 0 && $k < $this->col) {
      $this->reverse($data, $i, $j - 1, $k + 1);
      echo("  ". $data[$j][$k]);
    }
  }
  public  function zigzag($data) {
    $counter = 0;
    $i = 0;
    $j = 0;
    $k = 0;
    while ($i < $this->row) {
      if ($counter % 2 == 0) {
        $j = 0;
        while ($j <= $i && $j < $this->col && $i - $j >= 0) {
          echo("  ". $data[$i - $j][$j]);
          $j++;
        }
      } else {
        $j = $i;
        $k = 0;
        while ($j >= 0 && $j < $this->col && $k <= $i) {
          echo("  ". $data[$k][$j]);
          $j--;
          $k++;
        }
      }
      $i++;
      $counter++;
    }
    $i = 1;
    while ($i < $this->col) {
      if ($counter % 2 == 0) {
        $j = $this->row - 1;
        $k = $i;
        while ($j >= 0 && $k < $this->col) {
          echo("  ". $data[$j][$k]);
          $j--;
          $k++;
        }
      } else {
        $this->reverse($data, $i, $this->row - 1, $i);
      }
      $counter++;
      $i++;
    }
  }
}

function main() {
  $arr = array(
    array(1, 2, 3, 4), 
    array(6, 7, 8, 9), 
    array(11, 12, 13, 14), 
    array(16, 17, 18, 19), 
    array(1, 2, 3, 4)
  );
  $obj = new Matrix($arr);
  $obj->zigzag($arr);
}
main();

Output

  1  2  6  11  7  3  4  8  12  16  1  17  13  9  14  18  2  3  19  4
/*
 Node Js Program
 Zigzag traversal of Matrix
*/

class Matrix {
	
	constructor(arr) {
		this.row = arr.length;
		this.col = arr[0].length;
	}
	reverse(data, i, j, k) {
		if (j >= 0 && k < this.col) {
			this.reverse(data, i, j - 1, k + 1);
			process.stdout.write("  " + data[j][k]);
		}
	}
	zigzag(data) {
		var counter = 0;
		var i = 0;
		var j = 0;
		var k = 0;
		while (i < this.row) {
			if (counter % 2 == 0) {
				j = 0;
				while (j <= i && j < this.col && i - j >= 0) {
					process.stdout.write("  " + data[i - j][j]);
					j++;
				}
			} else {
				j = i;
				k = 0;
				while (j >= 0 && j < this.col && k <= i) {
					process.stdout.write("  " + data[k][j]);
					j--;
					k++;
				}
			}
			i++;
			counter++;
		}
		i = 1;
		while (i < this.col) {
			if (counter % 2 == 0) {
				j = this.row - 1;
				k = i;
				while (j >= 0 && k < this.col) {
					process.stdout.write("  " + data[j][k]);
					j--;
					k++;
				}
			} else {
				this.reverse(data, i, this.row - 1, i);
			}
			counter++;
			i++;
		}
	}
}

function main() {
	var arr = [
		[1, 2, 3, 4],
		[6, 7, 8, 9],
		[11, 12, 13, 14],
		[16, 17, 18, 19],
		[1, 2, 3, 4]
	];
	var obj = new Matrix(arr);
	obj.zigzag(arr);
}

main();

Output

  1  2  6  11  7  3  4  8  12  16  1  17  13  9  14  18  2  3  19  4
/*
 Swift 4 Program
 Zigzag traversal of Matrix
*/

class Matrix {
  var row: Int;
  var col: Int;
  init(_ arr: [[Int]] ) {
    self.row = arr.count;
    self.col = arr[0].count;
  }
  func reverse(_ data: [[Int]] , _ i : Int, _ j: Int, _ k: Int) {
    if (j >= 0 && k < self.col) {
      self.reverse(data, i, j - 1, k + 1);
      print(" ", data[j][k],terminator:"");
    }
  }
  func zigzag(_ data: [[Int]] ) {
    var counter: Int = 0;
    var i: Int = 0;
    var j = 0;
    var k = 0;
    while (i < self.row) {
      if (counter % 2 == 0) {
        j = 0;
        while (j <= i && j < self.col && i - j >= 0) {
          print(" ", data[i - j][j],terminator:"");
          j += 1;
        }
      } else {
        j = i;
        k = 0;
        while (j >= 0 && j < self.col && k <= i) {
          print(" ", data[k][j],terminator:"");
          j -= 1;
          k += 1;
        }
      }
      i += 1;
      counter += 1;
    }
    i = 1;
    while (i < self.col) {
      if (counter % 2 == 0) {
        j = self.row - 1;
        k = i;
        while (j >= 0 && k < self.col) {
          print(" ", data[j][k],terminator:"");
          j -= 1;
          k += 1;
        }
      } else {
        self.reverse(data, i, self.row - 1, i);
      }
      counter += 1;
      i += 1;
    }
  }
}
func main() {
  let arr: [[Int]] = [
    [1, 2, 3, 4],
    [6, 7, 8, 9],
    [11, 12, 13, 14],
    [16, 17, 18, 19],
    [1, 2, 3, 4]
  ];
  let obj: Matrix = Matrix(arr);
  obj.zigzag(arr);
}
main();

Output

  1  2  6  11  7  3  4  8  12  16  1  17  13  9  14  18  2  3  19  4


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved