Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
brilliant solution! but you need a bounds check on i<N and (D-i)<N before printing.
for(int D=0;D<=2*(N-1);D++) {
for (int i=0;i<=D;i++) {
if(i<N && (D-i)<N)
System.out.print(a[i][D-i]);
}
System.out.println();
}
for(int d = 0; d < 2 * x; d++) {
int a= 0;
if( d >= x)
a = (d%x) + 1;
for( int i = (0+ a); i <= (d - a); i++)
cout<< matrix[i][d-i];
cout<<endl;
}
this only works for NxN matrix if it MxN matrix your solution will not work.
it is a recursive problem you need to think in it recursively first.
#include <iostream>
using namespace std;
const int tw=3,th=3;
void printRow(int a[th][tw],int h,int w){
for(int i=0;i<w;i++){
cout<<a[h][i];
}
}
void printCol(int a[th][tw],int h,int w){
for(int i=h;i<th;i++){
cout<<a[i][w];
}
}
void printDiagonalR(int a[th][tw],int h,int w){
if(h>th) return;
printRow(a,h,w);
if(w<0) return;
printCol(a,h,w);
string spaces="";
for(int i=0;i<h+1;i++){
spaces+=" ";
}
cout<<endl<<spaces;
printDiagonalR(a,h+1,w-1);
}
int main(int argc, const char * argv[]) {
int a[th][tw]={{1,2,3},
{4,5,6,},
{7,8,9}};
printDiagonalR(a,0,tw-1);
return 0;
}
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
// insert code here...
int arr[3][3]={{1,2,3},{4,5,6},{7,8,9}};
int n=3;
for(int dsum=0; dsum<2*n-1; dsum++){
for(int i=0; i<=dsum; i++){
if(i<n and (dsum-i)<n)
cout<<arr[i][dsum-i]<<" ";
}
cout<<endl;
}
return 0;
}
public static void main(String args[]) throws Exception
{
int[][] a = {{1,2,3},{4,5,6},{7,8,9}};
print(a,3,3);
}
static void print(int[][] a,int rowmax,int colmax){
int row=0;
for(int i=0;i< colmax;i++)
printdiag(a,row,i,rowmax,colmax);
int col=colmax-1;
for(int i=1;i< rowmax;i++)
printdiag(a,i,col,rowmax,colmax);
}
static void printdiag(int[][] a,int row,int col,int rowmax,int colmax)
{
System.out.println();
while(row<rowmax && col >=0)
{
System.out.print(a[row][col]);
row++;
col--;
}
return;
}
#include <iostream>
using namespace std;
const int N = 4;
int main()
{
int A[N][N];
int n = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
A[i][j] = n++;
cout << A[i][j] << " ";
}
cout << endl;
}
for (int k = 0; k < 2 * N; k++) {
int i = k < N ? 0 : k - N + 1;
int j = k < N ? k : N - 1;
while (i < N && j >= 0)
cout << A[i++][j--] << " ";
cout << endl;
}
return 0;
}
We may print from right up to right left down, following is C++ code:
/*
------->x
|
|
|
y
*/
void printMatrixDiagonally(int** matrix, int row, int col)
{
int y, x;
pair<int,int> rightUp(0, 0), leftDown(0,0); //(y, x)
while(rightUp.first < row){
//print from right up to left down
for(y = rightUp.first, x = rightUp.second; y <= leftDown.first; ++y, ++x){
printf("%d ", matrix[y][x]);
}
puts("");
//move rightUp and leftDown
if(rightUp.second + 1 < col) ++rightUp.second;
else ++rightUp.first;
if(leftDown.first + 1 < row) ++leftDown.first;
else ++leftDown.second;
}
}
public class PrintMatrixDiagonally {
public static void main(String[] args) {
int m=4, n=4;
int arr[][]={{1,2,3,4},{5,6,7,8},{9,3,6,2},{4,7,9,0}};
int diagonals=n+m-1;
int i=0,j=0;
while(diagonals>0)
{
int k=i,l=j;
while(l>=0 && k<m)
{
System.out.print(arr[k][l]+" ");
l--;
k++;
}
System.out.println();
if(j<(n-1))
j++;
else
i++;
diagonals--;
}
}
}
public class Test{
public static void main(String[] args){
int n = 2;
int m = 5;
int[][] matrix = new int[n][m];
fillMatrix(matrix,n,m);
printDiagonal(matrix,n,m);
}
public static void fillMatrix(int[][] matrix,int n,int m){
int i = 1;
for(int l = 0; l < n; l++){
for(int k = 0; k < m; k++){
matrix[l][k] = i++;
}
}
}
public static void printDiagonal(int[][] matrix,int n,int m){
StringBuilder sb = new StringBuilder();
int dMax = n+m-1;
int d = 0;
for(d = 0; d < m; d++){
for(int l = 0; l <= d && l < n; l++){
sb.append(matrix[l][d-l]);
sb.append(" ");
}
sb.append("\n");
}
//pos diagonal
while(d <= dMax){
for(int l = d-m+1; l <= d && l < n ; l++){
sb.append(matrix[l][d-l]);
sb.append(" ");
}
sb.append("\n");
d++;
}
System.out.println(sb.toString());
}
}
function getDiagnols(array) {
var result = [];
var num_rows = array.length;
var num_columns = array[0].length;
for (var col_diagnol=0; col_diagnol < num_columns; col_diagnol+=1)
{
var diagnol =[];
for( var row =0, col=col_diagnol; row < num_rows && col >=0 ;row+=1, col-=1)
{
diagnol.push(array[row][col]);
}
result.push(diagnol);
}
for (var row_diagnol=1; row_diagnol < num_rows; row_diagnol+=1)
{
var diagnol =[];
for( var row = row_diagnol,col = num_columns-1; row < num_rows && col >= 0; row+=1,col-=1)
{
diagnol.push(array[row][col]);
}
result.push(diagnol);
}
return result;
}
var input = [[1,2,3],[4,5,6],[7,8,9]];
var input2 = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
var input3 = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
var input4 = [[1,2,3],[4,5,6],[7,8,9],[10,11,12]];
getDiagnols(input4);
public class DiagonalPrint {
public static void printAll(int[][] arr) {
for (int x = 0; x < arr[0].length; ++x) {
printOne(arr, x, 0);
}
for (int y = 1; y < arr.length; ++y) {
printOne(arr, arr[0].length - 1, y);
}
}
public static void printOne(int[][] arr, int x, int y) {
while (x >= 0 && y < arr.length) {
System.out.print(arr[y++][x--] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[][] arr = { { 1, 2, 4 }, { 3, 5, 7 }, { 6, 8, 9 } };
printAll(arr);
System.out.println();
int[][] arr1 = { { 1, 2, 4 }, { 3, 5, 7 }, { 6, 8, 10 }, { 9, 11, 12 } };
printAll(arr1);
System.out.println();
int[][] arr2 = { { 1, 2, 4, 7 }, { 3, 5, 8, 10 }, { 6, 9, 11, 12 } };
printAll(arr2);
System.out.println();
}
}
import java.io.*;
import java.util.*;
public class PrintDiagonalElements {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int N = Integer.parseInt(br.readLine());
int[][] mat = new int[N][N];
StringTokenizer st = null;
for (int i = 0; i < N; ++i) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; ++j) {
mat[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int sum = 0; sum < N; ++sum) {
String prefix = "";
for (int i = 0; i <= sum; ++i) {
int j = sum-i;
out.print(prefix);
out.print(mat[i][j]);
prefix = " ";
}
out.println();
}
for (int sum = N; sum <= 2*N-2; ++sum) {
String prefix = "";
for (int i = sum-N+1; i < N; ++i) {
int j = sum-i;
out.print(prefix);
out.print(mat[i][j]);
prefix = " ";
}
out.println();
}
out.flush();
out.close();
System.exit(0);
}
}
public static void printMatrix(int [][] a)
{
int m = a.length -1;
int n = a[0].length -1;
for (int i = 0; i <= m; i++)
{
printDiagonal(a, i, 0, n);
}
for (int j = 1; j <= n; j++)
{
printDiagonal(a, m, j, n);
}
}
public static void printDiagonal(int[][] a, int m, int n, int maxN)
{
int pm = m;
int pn = n;
while(!(pn > maxN))
{
//System.out.print(pm + "." + pn + " ");
System.out.print(a[pm][pn] + " ");
if(pm == n && pn ==m)
{
break;
}
pm--;
pn++;
}
System.out.println();
}
#include<iostream>
#include<conio.h>
/*
Give a N*N matrix, print it out diagonally.
Follow up, if it is a M*N matrix, how to print it out.
Example:
1 2 3
4 5 6
7 8 9
print:
1
2 4
3 5 7
6 8
9
*/
using namespace std;
int a[100][100];
void printdiagonal(int a[][100],int m,int n)
{
int x=0;
while(x<=n+1)
{
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
if(i+j==x)
cout<<a[i][j]<<" ";
}
}
cout<<"\n";
x++;
}
}
int main()
{
int m,n;
cout<<"\nEnter the number of rows:";
cin>>m;
cout<<"\nEnter the number of columns:";
cin>>n;
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
cin>>a[i][j];
}
printdiagonal(a,m,n);
getch();
return 0;
}
This print for both N * N and M * N
public class PrintDiagonally {
public static void print(int a[][]){
if (a == null || a.length == 0) return;
int numRows = a.length;
int numCols = a[0].length;
for (int j = 0; j < numCols; j++){
for (int i = 0, k = j; i < numRows && k >= 0; i++, k--){
System.out.print(a[i][k] + ",");
}
System.out.println();
}
for (int i = 1; i < numRows; i++){
for (int j = numCols - 1, k = i; k < numRows && j >= 0; k++, j--)
System.out.print(a[k][j] + ",");
System.out.println();
}
}
public static void main(String[] args){
int[][] a = new int[3][7];
for (int i = 0; i < a.length; i++)
for (int j = 0; j < a[i].length; j++)
a[i][j] = j+1;
print(a);
}
}
here the solution for MxN
public static void printDiagonally(int[][] matrix){
int N = matrix.length;
int M = matrix[0].length;
for (int c = 0; c < M ; c++) {
System.out.println("");
for (int d = 0; (c - d) >= 0 && d <= N - 1; d++) {
System.out.print(matrix[d][c - d] + " ");
}
}
for (int r = 1; r < M ; r++) {
System.out.println("");
int c = M-1;
for (int d = r; (c) >= r && d <= N - 1; d++) {
System.out.print(matrix[d][c] + " ");
c--;
}
}
}
public static void printDiag(int[][] A; int M; int N)
{
int T = (M-1) + (N-1);
for(int p = 0; p <= T; p++)
{
int i = 0, j = p;
// we add this to check p>=N, if yes it will go out of bound for j
if (p >= N)
{
int x = p-N+1;
i = i + x;
j = j - x;
}
while ((i < N) && (j >= 0))
{
system.out.print(A[i][j]);
i = i + 1;
j = j - 1;
}
system.out.println();
}
}
This can be problem can be treated in different way.
If the top-left element is considered as root of the tree , then this problem boils down to level order traversal of the tree.
Only one special handling is required
1. If it's the right most element in the considered tree or the top row in the current diagonal, just push its right and then bottom element.
2. For other elements in the current diagonal, just push the bottom element.
Do this until any element left in the queue.
typedef std::pair <int, int> position; //<x,y>
bool isVisible (int x, int y, int r, int c)
{
return (x >= 0 && x < r && y >= 0 && y < c);
}
void printMatrixDiagonally (int matrix[][MAX], int r, int c)
{
queue<position> q;
int diagCount = 1; // counts how may elements are present in that diagonal level
position start;
start = make_pair (0,0);
q.push(start);
while (!q.empty())
{
for (int i = 0 ; i < diagCount; i++)
{
position xy = q.front();
printf ("%d ", matrix[xy.first][xy.second]);
//special handling if the diagonal level contains only one entry
if (i == 0)
{
if (isVisible(xy.first, xy.second + 1, r, c))
{
start = make_pair (xy.first, xy.second + 1); // right
//printf ("Pushing (%d,%d)\n", start.first, start.second);
q.push (start);
}
if (isVisible(xy.first + 1, xy.second, r, c))
{
start = make_pair(xy.first + 1, xy.second); // bottom
//printf ("Pushing (%d,%d)\n", start.first, start.second);
q.push (start);
}
}
else // for all other
{
if (isVisible(xy.first + 1, xy.second, r, c)) // just play with bottom
{
start = make_pair(xy.first + 1, xy.second); // bottom
//printf ("Pushing (%d,%d)\n", start.first, start.second);
q.push (start);
}
}
q.pop();
}
diagCount = q.size();
printf ("\n");
}
}
//visual studio 2010
typedef unsigned char BYTE;
void zigzag_f(BYTE z[9], BYTE m[3][3])
{
int index = 0;
int x = 0;
int y = 0;
int tmp = 0;
int mode =0; //0 : ++ , 1: --
for(;;)
{
for(y = 0;y<x;y++)
{
if(index < 9)
{
tmp = z[index];
printf("%d",m[tmp/3][tmp % 3] );
index++;
}
else
break;
}
printf("\n");
if(mode == 0)
x++;
else if(mode == 1)
x--;
if(x==4)
{
mode = 1;
x=2;
}
else if(x==0)
break;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
BYTE z[9] = {0,1,3,2,4,6,5,7,8};
BYTE m[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
zigzag_f(z,m);
return 0;
}
public void do_prt_diag() {
int a[][] = { {1,2,3}, {4,5,6}, {7,8,9} };
// int a[][] = { {1,2,3,4,22}, {5,6,7,8,33}, {9,10,11,12,44} };
int j = 0;
int k = 0;
printDiagonally(a);
}
// start row then column
// start at a[y][x], where y=0..n-1 and x=0...m-1 go down and left till out of bound.
// start at a[y][x], where y=1..n-1 and x=m-1..0 go down and left till out of bound.
private void printDiagonally(int[][] a) {
int n = a.length; // col
int m = a[0].length; // row
int x = 0;
int y = 0;
// do row
for (int i = 0; i<m; i++) {
x=i;
while(x >= 0 && y <= n-1) {
System.out.print(a[y][x] + " ");
x--;
y++;
}
y=0; //reset column
System.out.println();
}
//do column
x=m-1;
for(int i=1; i<n; i++) {
y=i;
while(x>=0 && y<=n-1) {
System.out.print(a[y][x] + " ");
y++;
x--;
}
x=m-1; //rest row
System.out.println();
}
}
for a matrix of MxN, we will have a total of M+N-1 diagonals
at diagonal no. 0 - > we preint 0,0
at 1 -> 1,0 and 0,1
at 2 -> 2,0 1,1 and 0,2
See the pattern? for diagonal i, we print [ i-j ][ j ] for each j from 0 to i inclusive
public class Diagonal {
static int [][]mat = {{1,2,3},
{4,5,6},
{7,8,9}};
public static void main(String[] args) {
int totalDiagonals = mat.length + mat[0].length - 1;
for(int i = 0; i < totalDiagonals; i++ )
{
for(int j=0; j<=i; j++)
if(i-j<mat.length&&j<mat[0].length)
System.out.print(mat[i-j][j]+ " ");
System.out.println();
}
}
}
I just took a generic nxm matrix. It should work for square matrices as well... You can pass the matrix as an argument too
import numpy as npy
def printMatrix():
m = npy.matrix('9 7 6; 5 4 3; 6 7 2; 3 4 8; 6 7 2; 3 4 8')
(num_rows, num_cols) = m.shape
#print m
for c in xrange(num_cols):
row_index = 0
for c1 in reversed(xrange(0, c+1)):
if row_index >= num_rows:
continue
print(m[row_index, c1]),
row_index += 1
print("\n"),
for r in xrange(1, num_rows):
col_index = num_cols - 1
for r1 in xrange(r, num_rows):
if col_index < 0:
continue
print(m[r1, col_index]),
col_index -= 1
print("\n"),
def main():
# print matrix in a weird way :)
printMatrix()
if __name__ == '__main__':
main()
Heres solution in c#:
namespace MatrixPrint
{
class MainClass
{
public static int[,] matrix = new int[,]{{1,4,7}, {2,5,8}, {3,6,9}};
public static void Main (string[] args)
{
Console.WriteLine(matrix.GetLength(0));
for(int i = 0; i < matrix.GetLength(0); i++) {
for(int j = i, k = 0; (j >= 0 && k < matrix.GetLength(1)); j--, k++) {
Console.Write(matrix[j,k] + ", ");
}
Console.WriteLine("");
}
for (int i = 1; i < matrix.GetLength(1); i++) {
for(int j = matrix.GetLength(1)-1, k = i; k < matrix.GetLength(1) && j > 0; j--, k++) {
Console.Write(matrix[j,k]+ ", ");
}
Console.WriteLine("");
}
}
}
}
import java.util.List;
public DiagonalMatrix(List<List<Integer>> matrix) {
for(int i = 0; i < 2*matrix.size()-1; i++) {
printLine(matrix, i);
}
}
private void printLine(List<List<Integer>> matrix, int i) {
if(i < matrix.size()) {
printDiagonal(matrix, i, 0);
} else {
printDiagonal(matrix, matrix.size()-1, i - matrix.size()+1);
}
}
private void printDiagonal(List<List<Integer>> matrix, int x, int y) {
while(x >= 0 && y < matrix.size()) {
System.out.print(matrix.get(y).get(x) + " ");
x--;
y++;
}
System.out.println();
}
public class printMatrixDiagonally {
public static void main(String[] args){
int row = 2 , col =3;
int[][] input = new int[row][col];
for(int i =0 ; i< row ; i++){
for(int j= 0 ; j<col ;j ++){
input[i][j] = i+j;
}
}
printStack(input);
//Here is to print it out diagonally.
printStackDiag(input);
}
//this method is to print out the matrix.
public static void printStack(int[][] input){
int row = input.length, col = input[0].length;
for(int i =0 ;i <row ; i++){
for(int j=0 ; j<col ;j++){
System.out.print(" "+input[i][j]);
}
System.out.println();
}
}
public static void printStackDiag(int[][] input){
//. We need to print one line where their sum of i, j index is the same.
//total is the max of i, j sum.
int row = input.length , col = input[0].length, total = row+col -2 , sum = 0;
while(sum>=0 && sum <= total){
for(int i = 0 ; i< row ; i++){
int j= sum -i;
if(j>=0 && j< col){
System.out.print(" "+input[i][j]);
}
}
sum++;
System.out.println();
}
}
}
C# Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Test
{
class Program
{
static void Main(string[] args)
{
var n = 3;
var ip = new int[n,n];
ip[0, 0] = 1;
ip[1, 0] = 2;
ip[2, 0] = 3;
ip[1, 0] = 4;
ip[1, 1] = 5;
ip[1, 2] = 6;
ip[2, 0] = 7;
ip[2, 1] = 8;
ip[2, 2] = 9;
MyMethod(ip,n);
Console.ReadKey();
}
static IEnumerable<int> MyMethod(int[,] ip, int n)
{
var output = new List<int>();
for (var i = 0; i <= 2 * (n - 1); i++)
{
var iTemp = i;
for (var j = 0; j <= i; j++)
{
if (iTemp >= 0 && iTemp < n && j >= 0 && j < n)
{
Console.WriteLine(iTemp + " " + j);
}
iTemp = iTemp - 1;
}
Console.WriteLine("inner loop ends");
}
return output;
}
}
}
#include <stdio.h>
int main()
{
int mat[5][5],i,j,k,m;
scanf("%d",&m);
for(i=0;i<m;i++)
for(j=0;j<m;j++)
scanf("%d",&mat[i][j]);
for(i=0;i<m;i++)
{
for(k=0,j=i;j>=0;j--,k++)
printf("%d ",mat[k][j]);
printf("\n");
}
for(i=1;i<m;i++)
{
for(j=m-1,k=i;k<m;k++,j--)
printf("%d ",mat[k][j]);
printf("\n");
}
return 0;
}
following should work for both nxn and nxm matrix
int [][] A = new int [N][M];
int nBound = 0, mBound = 0, n = 0;
for(int i = 0; i < (M + N - 1); i++){
n = nBound;
for(int y = mBound; y >= 0; y--){
System.out.print(A[n][y]);
if(n == N - 1)break;
n++;
}
System.out.println();
if(mBound < M - 1){
mBound++;
}else {
nBound++;
}
}
#include <iostream>
void print(int a[][3], int dim)
{
for (int i = 0; i < dim; ++i)
{
int y = i; int x = 0;
do
{
std::cout << a[x][y] << ",";
--y; ++x;
} while (y >= 0);
std::cout << "\n";
}
for (int i = 1; i < dim; ++i)
{
int y = dim - 1; int x = i;
do
{
std::cout << a[x][y] << ",";
--y; ++x;
} while (x <= dim - 1);
std::cout << "\n";
}
}
int main()
{
int a[][3] = {{1,2,3},{4,5,6},{7,8,9}};
print(a, 3);
return 0;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace DiagonalMatrixPrint
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter the no of rows and columns");
int rowCount = int.Parse(Console.ReadLine());
int colCount = int.Parse(Console.ReadLine());
int[,] matrix = new int[rowCount, colCount];
var random = new Random(1);
for(int i = 0 ; i < rowCount; i++)
{
for(int j = 0; j < colCount; j++)
{
matrix[i, j] = random.Next(10);
Console.Write(matrix[i, j]);
Console.Write(" ");
}
Console.WriteLine("");
}
PrintDiagonally(matrix);
}
private static void PrintDiagonally(int[,] matrix)
{
int rowCount = matrix.GetLength(0);
int colCount = matrix.GetLength(1);
for(int i = 0; i < colCount; i++)
{
int rowIdx = 0;
int colIdx = i;
while(rowIdx < rowCount && colIdx < colCount && colIdx >= 0 && rowIdx >= 0)
{
Console.Write(matrix[rowIdx, colIdx]);
rowIdx++;
colIdx--;
}
Console.WriteLine("");
}
for (int i = 1; i < rowCount; i++)
{
int rowIdx = i;
int colIdx = colCount - 1;
while (rowIdx < rowCount && colIdx < colCount && colIdx >= 0 && rowIdx >= 0)
{
Console.Write(matrix[rowIdx, colIdx]);
rowIdx++;
colIdx--;
}
Console.WriteLine("");
}
}
}
}
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int** createMatrix(int rows, int cols);
void fillMatrix(int **matrix, int rows, int cols);
void printMatrixNormal(int **matrix, int rows, int cols);
void printMatrixDiagonal(int **matrix, int rows, int cols);
int main(void)
{
int rows;
int cols;
int **matrix;
printf("Rows: ");
scanf("%d", &rows);
printf("Cols: ");
scanf("%d", &cols);
matrix = createMatrix(rows, cols);
fillMatrix(matrix, rows, cols);
printf("\n");
printMatrixNormal(matrix, rows, cols);
printf("\n");
printMatrixDiagonal(matrix, rows, cols);
return 0;
}
int** createMatrix(int rows, int cols)
{
int **matrix;
matrix = new int*[rows];
for(int row = 0; row < rows; row++)
{
matrix[row] = new int[cols];
}
return matrix;
}
void fillMatrix(int **matrix, int rows, int cols)
{
srand(time(NULL));
for(int row = 0; row < rows; row++)
{
for(int col = 0; col < cols; col++)
{
matrix[row][col] = rand() % 10;
}
}
}
void printMatrixNormal(int **matrix, int rows, int cols)
{
for(int row = 0; row < rows; row++)
{
for(int col = 0; col < cols; col++)
{
printf("%d ", matrix[row][col]);
}
printf("\n");
}
}
void printMatrixDiagonal(int **matrix, int rows, int cols)
{
for(int maxRow = 0; maxRow < rows; maxRow++)
{
for(int row = 0; row <= maxRow; row++)
{
printf("%d ", matrix[row][maxRow - row]);
}
printf("\n");
}
for(int startRow = 1; startRow < rows; startRow++)
{
for(int row = startRow; row < rows; row++)
{
printf("%d ", matrix[row][cols - (row - startRow) - 1]);
}
printf("\n");
}
}
package com.google.practice;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
class Pos{
public int x;
public int y;
public int level;
public Pos(int x,int y,int level){
this.x = x;
this.y = y;
this.level = level;
}
}
public class DiagonalPrint {
public static void main(String[] arg){
int[][] mat = {{1,2},{5,6},{9,10}};
int n=mat.length;
int m=mat[0].length;
//printDiagonally(mat,n,m);
printDiagonallyBFS(mat,0,0,n,m);
}
public static void printDiagonally(int[][] mat,int n,int m){
for(int i=0,j=0;i<n;){
for(int k=j-i,inc=0;k>=0;k--,inc++){
System.out.print(mat[i+inc][j-inc]);
}
System.out.println();
if(j==m-1)
i++;
else
j++;
}
}
public static void printDiagonallyBFS(int[][] mat,int i,int j,int n,int m){
int level = 1;
Map<Integer,String> matVal = new HashMap<Integer,String>();
Queue<Pos> q = new LinkedList<Pos>();
matVal.put(level, mat[i][j]+" ");
q.add(new Pos(i,j,1));
while(!q.isEmpty()){
Pos u = q.poll();
i = u.x;
j = u.y;
int l = u.level;
//right
if(i==0 && j<m-1){
Pos p = new Pos(i,j+1,l+1);
putInHash(i,j+1,l+1,matVal,mat);
q.add(p);
}
//down
if(i<n-1){
Pos p = new Pos(i+1,j,l+1);
putInHash(i+1,j,l+1,matVal,mat);
q.add(p);
}
}
printDiagonal(matVal);
}
public static void putInHash(int i,int j,int l,Map<Integer,String> matVal,int[][] mat){
if(matVal.containsKey(l)){
String s = matVal.get(l);
matVal.put(l, s+mat[i][j]+" ");
}else{
matVal.put(l, mat[i][j]+" ");
}
}
public static void printDiagonal(Map<Integer,String> matVal){
Set<Integer> levels = matVal.keySet();
for(int i : levels)
System.out.println(matVal.get(i));
}
}
BFS approach. Storing diagonals level wise. time O(nm)
//A simple code to do the job
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,k,x,y,m,n,a[10][10];
cout<<"Enter m and n\n";
cin>>m>>n;
cout<<"Enter the matrix\n";
for(i=0;i<m;i++)
for(j=0;j<n;j++)
cin>>a[i][j];
for(i=0,j=0;i<n;i++)
{
x=0;y=j;
while(x>=0&&x<m&&y>=0&&y<n)
{
cout<<a[x][y]<<" ";
x++;y--;
}
cout<<endl;
j++;
}
j=1;
for(i=0;i<m-1;i++)
{
x=j;y=n-1;
while(x>=0&&x<m&&y>=0&&y<n)
{
cout<<a[x][y]<<" ";
x++;y--;
}
cout<<endl;
j++;
}
return 0;
}
void helper(const vector<vector<int>> &matrix, int x, int y){
int m = matrix.size();
while(x>=0 && y<m){
cout << matrix[x][y] << “\t”;
--x;
++y;
}
cout << endl;
}
void printDiagonally(vector<vector<int>> matrix){
if(matrix.empty() || matrix[0].empty())
return;
int m = matrix.size(), n = matrix[0].size();
for(int i=0; i<n; ++i)
helper(matrix, 0, i);
for(int i=1; i<m; ++i)
helper(matrix, i, n-1);
}
public class DiagonalMatrix {
static void printMatrix(int[][] inp)
{
for(int i=0; i < inp[0].length;i++)
{
for(int x=0,y=i; y >=0;x++,y--)
System.out.print(inp[x][y]+" ");
System.out.println();
}
//System.out.println("----------");
for(int i=1;i < inp.length;i++)
{
for(int x=i,y=inp[0].length-1;x < inp.length;x++,y--)
System.out.print(inp[x][y]+" ");
System.out.println();
}
}
public static void main(String[] args) {
int[][] inp={{1,2,3},{4,5,6},{7,8,9}};
printMatrix(inp);
}
}
This works for NxM matrix. For a given element data(i)(j), the sum of the two indexes ranges between 0 and m+n-1. For a given row in the matrix we need to efficiently compute the start and end column index, which is Min(i, n-1) to Max(0, i-m+1) in descending order.
Implemented in scala:
def diagonalPrint(data:Seq[Seq[Int]]) = {
require(data.length>0)
val (m, n) = (data.length, data(0).length)
for(i<-0 until m+n-1) {
for (j<-Math.min(i, n-1) to Math.max(0, i-m+1) by -1) {
print(data(i-j)(j))
print(" ")
}
println
}
}
val data = Seq.tabulate(5,4)((i,j)=>i*4+j+1)
println(data)
diagonalPrint(data)
Solution for N*N and N*M in C++ with vectors:
#include <iostream>
#include <vector>
void printDiagonal(const std::vector<std::vector<int> > &input)
{
int N = input.size();
int M = 0;
if (N > 0)
M = input[0].size();
int L = N + M - 1;
int vert = 0;
int horiz = 0;
std::cout << N << " x " << M << " matrix. " << std::endl;
for (int i = 0; i < L; ++i){
for (int horiz = 0; horiz < N; ++horiz){
for (int vert = 0; vert < M; ++vert){
if (horiz+vert == i)
std::cout << input[horiz][vert] << " ";
}
}
std::cout << std::endl;
}
}
int main()
{
std::vector<std::vector<int> > inputVec {{1,2,3},{4,5,6},{7,8,9}};
std::vector<std::vector<int> > inputVec2 {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
printDiagonal(inputVec);
std::cout << std::endl;
printDiagonal(inputVec2);
return 0;
}
The basic idea is to start from top line, and right line. For each start point (i,j), continuously print the (i+1,j-1).
My code:
import java.awt.Point;
public class DiagonalPrintMatrix {
public static void main(String[] args){
int[][] matrix = {
{1,2,3},
{4,5,6},
{7,8,9}
};
printMatrix(matrix);
}
public static void printMatrix(int[][] matrix){
for(int i=0;i<matrix.length;i++){
//start from top line
Point p = new Point(0, i);
while(p!=null){
p = printMatrix(matrix, p);
}
System.out.println();
}
for(int i=1;i<matrix.length;i++){
//start from the right line
Point p = new Point(i, matrix.length-1);
while(p!=null){
p = printMatrix(matrix, p);
}
System.out.println();
}
}
public static Point printMatrix(int[][] matrix, Point p){
System.out.print(matrix[p.x][p.y]+" ");
if(p.x+1>matrix.length-1||p.y-1<0){
return null;
}
return new Point(p.x+1, p.y-1);
}
}
let i be row number (0 to N-1), and j be col number (O to N-1)
diagonal 1 has i+j =0
diagonal 2 has i+j =1
...
So define D = i+j
Loop with D from 0 to 2*(N-1)
Now if D = i+j then j=D-i
So we have reduced the problem to two variables: D and i (two loops)
Check for bugs. And thanks for posting this fun question.
- S O U N D W A V E February 28, 2014You can think of the MxN case