Google Interview Question Dev Leads
-2of 2 votesWrite code to traverse a NxM matrix in a zig-zag fashion
Country: United States
Interview Type: In-Person
This can be done in O(n^2) (have to traverse each of the elements in the matrix).
I did this by first printing the upper-left triangle in the matrix (with the opposite/minor diagonal inclusive) and then printing the bottom-right triangle (minor diagonal exclusive). Just involves some index play and need to make sure you don't get an ArrayOutOfBoundsException.
Below solution is in Java:
public class PrintZigZag {
public static void main(String[] args) {
int[][] test1 = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
printZigZag(test1);
System.out.println(); // new line for a new test
int[][] test2 = new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
printZigZag(test2);
}
// matrix is N x N
public static void printZigZag(int[][] matrix) {
int len = matrix.length;
// upper left triangle (including minor diagonal)
for(int i=1; i<=len; i++) {
for(int j=1; j<=i; j++) {
int next = matrix[i - j][j-1];
System.out.print(next + " ");
}
}
// lower right triangle (excluding minor diagonal)
for(int i=1; i<len; i++) {
for(int j=i; j<len; j++) {
int next = matrix[len + i - j - 1][j];
System.out.print(next + " ");
}
}
}
}
Running above two tests yields:
1 4 2 7 5 3 8 6 9
1 5 2 9 6 3 13 10 7 4 14 11 8 15 12 16
Oops, didn't read the question too well. A solution for N x M matrix is required. Slight changes to the above code does the trick:
public class PrintZigZag {
public static void main(String[] args) {
int[][] test1 = new int[][]{{1, 2}, {4, 5}, {7, 8}};
printZigZag(test1);
System.out.println(); // new line for a new test
int[][] test2 = new int[][]{{1, 2, 3}, {5, 6, 7}, {9, 10, 11}, {13, 14, 15}};
printZigZag(test2);
}
// matrix is N x N
public static void printZigZag(int[][] matrix) {
int N = matrix.length;
int M = matrix[0].length;
// upper left triangle (including minor diagonal)
for(int i=1; i<=N; i++) {
for(int j=1; j<=Math.min(M, i); j++) {
int next = matrix[i - j][j-1];
System.out.print(next + " ");
}
}
// lower right triangle (excluding minor diagonal)
for(int i=1; i<M; i++) {
for(int j=i; j<M; j++) {
int next = matrix[N + i - j - 1][j];
System.out.print(next + " ");
}
}
}
}
If you're dealing with sparse matrices you might want to take a slightly different approach. This algorithm runs in O(n log n), where n is the number of non-zero entries.
# Matrix element
class Element(object):
def __init__(self, row, col, val):
self.row = row
self.col = col
self.val = val
return
# Coordinate list matrix class
class Matrix(object):
def __init__(self):
self.rows = 0
self.cols = 0
self.elements = list()
return
def add(self, e):
assert type(e) is Element
self.elements.append(e)
if e.row > self.rows:
self.rows = e.row
if e.col > self.cols:
self.cols = e.col
return
class ZZIter(object):
def __init__(self, matrix):
assert type(matrix) is Matrix
elements = sorted(matrix.elements, key=lambda x: x.row)
elements = sorted(elements, key=lambda x: x.row + x.col)
self.elements = elements
self.index = 0
return
def __iter__(self):
return self
def __next__(self):
if self.index == len(self.elements):
raise StopIteration
e = self.elements[self.index]
self.index += 1
return e
You might want to take a different approach if you're dealing with sparse matrices. This runs in O(n log n), where n is the number of non-zero entries. This assumes zig-zag means going bottom-left to top right for each diagonal. If you want to alternate direction you need to sort each diagonal separately, I think.
# Matrix element
class Element(object):
def __init__(self, row, col, val):
self.row = row
self.col = col
self.val = val
return
# Coordinate list matrix class
class Matrix(object):
def __init__(self):
self.rows = 0
self.cols = 0
self.elements = list()
return
def add(self, e):
assert type(e) is Element
self.elements.append(e)
if e.row > self.rows:
self.rows = e.row
if e.col > self.cols:
self.cols = e.col
return
class ZZIter(object):
def __init__(self, matrix):
assert type(matrix) is Matrix
elements = sorted(matrix.elements, key=lambda x: x.row)
elements = sorted(elements, key=lambda x: x.row + x.col)
self.elements = elements
self.index = 0
return
def __iter__(self):
return self
def __next__(self):
if self.index == len(self.elements):
raise StopIteration
e = self.elements[self.index]
self.index += 1
return e
function traverseDiagonal(n, m, matrix, sequence) {
while (matrix[n][m] !== undefined) {
sequence.push(matrix[n][m++])
if (matrix[--n] === undefined) {
return
}
}
}
module.exports = function (matrix) {
var sequence = []
var N = matrix.length
var M = matrix.length > 0 ? matrix[0].length : null
if (M === null) {
throw new Error('Length of `M` cannot be zero.')
}
var m, n
m = n = 0
for (; n < N; ++n) {
traverseDiagonal(n, m, matrix, sequence)
}
n--
m++
for (; m < M; ++m) {
traverseDiagonal(n, m, matrix, sequence)
}
return sequence
}
var matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
var sequence = module.exports(matrix)
console.log(sequence.toString())
public class MatrixZigZag {
public static void main(String[] args) {
// TODO Auto-generated method stub
Object[][] m1 = {{"a", "b", "c"},
{"d", "e", "f"},
{"g", "h", "i"},
{"j", "k", "l"}};
System.out.println(zigZag(m1, 0, 0));
// The above prints a b d c e g f h j i k l
Object[][] m2 = {{"a", "b", "c", "d"},
{"e", "f", "g", "h"}};
System.out.println(zigZag(m2, 0, 0));
// The above prints a b e c f d g h
}
public static String zigZag(Object[][] m, int i, int j) {
StringBuilder sb = new StringBuilder("");
while (true) {
sb.append(m[i][j].toString() + " ");
if (i == m.length - 1 && j == m[0].length - 1) {
break;
}
if (checkStart(m, i, j)) {
int[] symm = symmAfter(m, i, j);
i = symm[0];
j = symm[1];
} else {
i++;
j--;
}
}
return sb.deleteCharAt(sb.length() - 1).toString();
}
public static int[] symmAfter(Object[][] m, int i, int j) {
int[] newPos = new int[2];
newPos[0] = Math.max(0, i - m[0].length + 1 + j);
newPos[1] = Math.min(i + j, m[0].length - 1);
if (newPos[1] < m[0].length - 1) {
newPos[1]++;
} else {
newPos[0]++;
}
return newPos;
}
public static boolean checkStart(Object[][] m, int i, int j) {
if (i == m.length - 1 || j == 0) {
return true;
}
return false;
}
}
public List<Integer> printZigZagMatrix(int[][] matrix ){
List<Integer> result = new ArrayList<>();
int i=0,j=0;
int[] dx = {-1,1};//up,down
int[] dy = {1,-1};
int d=0;
int[] ex = {0,1};//right,down
int[] ey = {1,0};
int e = 0;
while(true){
result.add(matrix[i][j]);
//if no up, then go right and start coming down diagnally
//if no down go down and start going up
int ii = i+dx[d];
int jj = j+dy[d];
if(ii<0 || jj<0 || ii>=matrix.length || jj>=matrix[0].length){
//change direction
d = (d+1)%2;
if(i==matrix.length-1){
i = i+ex[0];
j = j+ey[0];
}else if(j==matrix[0].length-1){
i = i+ex[1];
j = j+ey[1];
}else{
i = i+ex[e];
j = j+ey[e];
}
result.add(matrix[i][j]);
if(i==matrix.length-1 && j==matrix[0].length-1){
break;
}
e = (e+1)%2;
}
i = i+dx[d];
j = j+dy[d];
}
return result;
}
public List<Integer> printZigZagMatrix(int[][] matrix ){
List<Integer> result = new ArrayList<>();
int i=0,j=0;
int[] dx = {-1,1};//up,down
int[] dy = {1,-1};
int d=0;
int[] ex = {0,1};//right,down
int[] ey = {1,0};
int e = 0;
while(true){
result.add(matrix[i][j]);
//if no up, then go right and start coming down diagnally
//if no down go down and start going up
int ii = i+dx[d];
int jj = j+dy[d];
if(ii<0 || jj<0 || ii>=matrix.length || jj>=matrix[0].length){
//change direction
d = (d+1)%2;
if(i==matrix.length-1){
i = i+ex[0];
j = j+ey[0];
}else if(j==matrix[0].length-1){
i = i+ex[1];
j = j+ey[1];
}else{
i = i+ex[e];
j = j+ey[e];
}
result.add(matrix[i][j]);
if(i==matrix.length-1 && j==matrix[0].length-1){
break;
}
e = (e+1)%2;
}
i = i+dx[d];
j = j+dy[d];
}
return result;
}
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class PrintMatrixZigZag {
private static int[][] arr;
private static int n;
private static int m;
private static Set<String> covered;
private static List<String> queue;
private static String sep = ":";
public static void main(String a[]) {
n = 3;
m = 4;
arr = new int[n][m];
arr[0] = new int[] { 1, 2, 3, 4 };
arr[1] = new int[] { 5, 6, 7, 8 };
arr[2] = new int[] { 9, 10, 11, 12 };
covered = new HashSet<String>();
queue = new ArrayList<String>();
queue.add(0 + sep + 0);
System.out.print(arr[0][0]+"\t");
while (queue.size() != 0) {
queue = printNum(queue);
}
}
private static List<String> printNum(List<String> queue) {
List<String> aux = new ArrayList<String>();
for (String tmp : queue) {
String[] inds = tmp.split(sep);
int i = Integer.parseInt(inds[0]);
int j = Integer.parseInt(inds[1]);
if (j == 0 && i < n-1) {
aux.add(i + 1 + sep + j);
System.out.print(arr[i + 1][j] + "\t");
}
if (j < m - 1 && !covered.contains(tmp)) {
aux.add(i + sep + (j + 1));
System.out.print(arr[i][j + 1] + "\t");
}
covered.add(tmp);
}
return aux;
}
}
private static void printZigZag(int[][] arr){
int rows=arr.length, columns=arr[0].length;
int i=0,j=0;
while (i<arr.length && j<arr[0].length){
System.out.print("\n"+arr[i][j]+"\t");
while(i>0 && j<columns-1){
i--;j++;
System.out.print(arr[i][j]+"\t");
}
if(j==columns-1)i++;
else if(i==0)j++;
if(i>=rows || j>=columns)break;
System.out.print("\n"+arr[i][j]+"\t");
while(i< rows-1 && j>0){
i++;j--;
System.out.print(arr[i][j]+"\t");
}
if(i==rows-1)j++;
else if(j==0)i++;
}
}
private static void printZigZag2(Matrix matrix) {
int ctr = 0;
int i = 0;
int j = 0;
final int m = matrix.getRows();
final int n = matrix.getCols();
while (ctr < (m * n)) {
System.out.println(matrix.getVal(i, j));
ctr++;
if (i == 0) {
while ((i != (m - 1)) || (j != 0)) {
i++;
j--;
}
if (i == (m - 1)) {
j++;
} else {
i++;
}
} else if (j == (n - 1)) {
while ((i != (m - 1)) || (j != 0)) {
i++;
j--;
}
if (i == (m - 1)) {
j++;
} else {
i++;
}
} else {
i--;
j++;
}
}
}
private static void printZigZag2(Matrix matrix) {
int ctr = 0;
int i = 0;
int j = 0;
final int m = matrix.getRows();
final int n = matrix.getCols();
while (ctr < (m * n)) {
System.out.println(matrix.getVal(i, j));
ctr++;
if (i == 0) {
while ((i != (m - 1)) || (j != 0)) {
i++;
j--;
}
if (i == (m - 1)) {
j++;
} else {
i++;
}
} else if (j == (n - 1)) {
while ((i != (m - 1)) || (j != 0)) {
i++;
j--;
}
if (i == (m - 1)) {
j++;
} else {
i++;
}
} else {
i--;
j++;
}
}
}
void zigzagTraversal(int a[][]){
if(a.length==0)
return;
int i=0;
int j=0;
int count=0;
while(i<a.length || count<a[0].length){
if(i>a.length-1){
i=a.length-1;
count++;
}
int row=i, column=count;
while(row>=0 && column<a[0].length){
System.out.print(a[row][column]);
row--;
column++;
}
i++;
}
}
- Chris January 05, 2017# assume due to feedbacks, zig-zag means # diagonals starting from upper-left, going down until # lower and if at bottom-left go to bottom-right # printing the elements into up-left diagonale # # e.g- the desired order in this case: # [[0, 1, 2, 3, 4], # [5, 6, 7, 8, 9], # [a, b, c, d, e]] # is: 0, 5, 1, a, 6, 2, b, 7, 3, c, 8, 4, d, 9, e # # or in this case: # [[0, 1] # [2, 3] # [4, 5]] # 0, 2, 1, 4, 3, 5 # # in python3: def traverse(matrix): cols = len(matrix[0]) rows = len(matrix) print('matrix {0}:'.format(matrix), end=' ') for i in range (0, rows): for j in range (0, min(i + 1, cols)): print(matrix[i - j][j], end= ' ') for j in range (1, cols): for i in range (0, min(cols - j, rows)): print(matrix[rows - i - 1][j + i], end=' ') print() traverse([[1,2,3],[4,5,6],[7,8,9]]) traverse([[0,1,2,3,4],[5,6,7,8,9],[10,11,12,13,14]]) traverse([[0,1],[2,3],[4,5]]) traverse([[1],[2],[3]]) traverse([[1, 2, 3]]) #output: #matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]]: 1 4 2 7 5 3 8 6 9 #matrix [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14]]: 0 5 1 10 6 2 11 7 3 12 8 4 13 9 14 #matrix [[0, 1], [2, 3], [4, 5]]: 0 2 1 4 3 5 #matrix [[1], [2], [3]]: 1 2 3 #matrix [[1, 2, 3]]: 1 2 3