Microsoft Interview Question SDE-2s
Country: United States
Interview Type: Phone Interview
package main.java.matrix;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* In given array find zero and replace the entire row and column with zeros
E.g Input:
1 2 3 4
5 6 7 8
9 10 0 11
12 13 14 15
Output:
1 2 0 4
5 6 0 8
0 0 0 0
12 13 0 15
* @author kuldeep
*
*/
public class MatrixZeroValueFinder {
int[][] array = new int[][]{
{1,2,3,4},
{5,6,7,8},
{9,10,0,12},
{13,0,15,16}
};
private List zeroIndexes = new ArrayList();
public void printArray(){
System.out.println("Printing Array");
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
System.out.print("\t"+array[i][j]);
}
System.out.println();
}
}
public void fillArrayForZeroValues(){
for (Iterator iter = zeroIndexes.iterator(); iter.hasNext();) {
ArrayIndex element = (ArrayIndex) iter.next();
int row = element.getRow();
int column = element.getColumn();
for (int i = 0; i < array[row].length; i++) {
array[row][i]=0;
}
for (int i = 0; i < array.length; i++) {
array[i][column]=0;
}
}
}
public void findZeroIndexes(){
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
if(array[i][j]==0){
zeroIndexes.add(new ArrayIndex(i,j));
}
}
}
}
public static void main(String[] args) {
MatrixZeroValueFinder finder = new MatrixZeroValueFinder();
finder.printArray();
finder.findZeroIndexes();
finder.fillArrayForZeroValues();
finder.printArray();
}
}
class ArrayIndex{
private int row;
private int column;
public ArrayIndex(int row,int column){
this.row=row;
this.column = column;
}
public int getColumn() {
return column;
}
public int getRow() {
return row;
}
}
Logic I Used:
1.scan the matrix row wise.
2.the moment you encounter 0 break from that iteration
3.Maintain 2 list called row and col that specify the row index and col index of 0(handles multiple occurence of 0).
4.Once the elements are scanned then fetch the row list and change it to 0.
(so this should happen column no of times)
5.fetch the col list and change it to 0.
(so this should happen row no of times).
Time Complexity:fetching 0 + changing to 0
O(mn)+O(n(m))+O(m(n))=O(mn)
import java.util.ArrayList;
import java.util.Random;
public class InitializeZero {
public static void trav(int [][] array, int row,int col){
ArrayList r = new ArrayList();
ArrayList c = new ArrayList();
for(int i = 0; i < row ; i++)
{
if(r.contains(i))
continue;
for(int j = 0; j < col ; j++){
if(c.contains(j))
continue;
if(array[i][j] == 0){
r.add(i);
c.add(j);
break;
}
}
}
for(int i = 0 ; i<r.size() ; i++ ){
int rowFetched = (int) r.get(i);
array[rowFetched] = new int[col];
/*for(int j = 0 ; j < col ; j++){
array[rowFetched][j]=0;
}*/
}
for(int i = 0 ; i<c.size() ; i++ ){
int colFetched = (int) c.get(i);
for(int j = 0 ; j < row ; j++){
array[j][colFetched]=0;
}
}
}
public static void display(int array[][], int row, int col){
System.out.println("\n\n");
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(array[i][j] + " ");
}
System.out.print("\n");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int row= 4;
int col = 6;
int[][] array1 = new int[row][col];
populate(array1,row,col);
display(array1,row,col);
trav(array1,row,col);
display(array1,row,col);
}
private static void populate(int[][] array,int row,int col) {
// TODO Auto-generated method stub
Random rand = new Random();
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
array[i][j]=rand.nextInt(col);
}
}
}
}
Logic I Used:
1.scan the matrix row wise.
2.the moment you encounter 0 break from that iteration
3.Maintain 2 list called row and col that specify the row index and col index of 0(handles multiple occurence of 0).
4.Once the elements are scanned then fetch the row list and change it to 0.
(so this should happen column no of times)
5.fetch the col list and change it to 0.
(so this should happen row no of times).
Time Complexity:fetching 0 + changing to 0
O(mn)+O(n(m))+O(m(n))=O(mn)
import java.util.ArrayList;
import java.util.Random;
public class InitializeZero {
public static void traverse(int [][] array,int row, int col){
int difference = Math.abs(row - col);
int smallest = Math.min(row, col);
int largest = Math.max(row, col);
for(int i=0;i<row-1;i++){
for(int j=0;j<col-1;j++){
System.out.println("\ta["+(i+1)+"]"+"["+(j+2)+"]:"+array[i][j+1]+"\t"
+"\ta["+(i+2)+"]"+"["+(j+1)+"]:"+array[i+1][j]+"\t");
}
System.out.println("\n");
}
for(int i = 0 ; i < difference ; i++){
}
}
public static void trav(int [][] array, int row,int col){
ArrayList r = new ArrayList();
ArrayList c = new ArrayList();
for(int i = 0; i < row ; i++)
{
if(r.contains(i))
continue;
for(int j = 0; j < col ; j++){
if(c.contains(j))
continue;
if(array[i][j] == 0){
r.add(i);
c.add(j);
break;
}
}
}
for(int i = 0 ; i<r.size() ; i++ ){
int rowFetched = (int) r.get(i);
array[rowFetched] = new int[col];
/*for(int j = 0 ; j < col ; j++){
array[rowFetched][j]=0;
}*/
}
for(int i = 0 ; i<c.size() ; i++ ){
int colFetched = (int) c.get(i);
for(int j = 0 ; j < row ; j++){
array[j][colFetched]=0;
}
}
}
public static void display(int array[][], int row, int col){
System.out.println("\n\n");
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(array[i][j] + " ");
}
System.out.print("\n");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int row= 4;
int col = 6;
int[][] array1 = new int[row][col];
populate(array1,row,col);
display(array1,row,col);
trav(array1,row,col);
display(array1,row,col);
}
private static void populate(int[][] array,int row,int col) {
// TODO Auto-generated method stub
Random rand = new Random();
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
array[i][j]=rand.nextInt(col);
}
}
}
}
/*
* Problem1: In given array find zero and replace the entire row and column with zeros
* Logic I Used:
1.scan the matrix row wise.
2.the moment you encounter 0 break from that iteration
3.Maintain 2 list called row and col that specify the row index and col index of 0(handles multiple occurence of 0).
4.Once the elements are scanned then fetch the row list and change it to 0.
(so this should happen column no of times)
5.fetch the col list and change it to 0.
(so this should happen row no of times).
Time Complexity:fetching 0 + changing to 0
O(mn)+O(n(m))+O(m(n))=O(mn)
*/
import java.util.ArrayList;
import java.util.Random;
public class InitializeZeroForSquareMatrix {
public void traverse(int [][]array, int row, int col){
for(int i = 0 ; i < row ; i++){
if(array[i][i] == 0){
}
}
}
public static void trav(int [][] array, int row,int col){
ArrayList r = new ArrayList();
ArrayList c = new ArrayList();
for(int i = 0; i < row ; i++)
{
/*this flag keeps track of how many 0 u encounter in each row
* Hence for each row the value should get initialized back to 0
*/
int flag = 0;
for(int j = 0; j< col ; j++){
/*
*for each column element in row i or simply put for each element in the row,
*check if its ==0 and if its not already present in the c list which stores the column position of 0
*the second condition is required coz i am changing the matrix value while scanning itself.
*so u may encounter 0 because of changed matrix and not the original matrix...
*/
if(array[i][j] == 0 && !c.contains(j)){
flag++;
c.add(j);
}
}
/*
* now no of 0's = flag
* step1: change row to 0.
* I know we need to traverse the array and change it to 0.but just used new int
*
* Step2 : change each column to 0 and iterate this flag no of times.
*/
if(flag != 0){
array[i] = new int[col];
for(int k = 0 ; k< flag; k++){
int columnTOBeChanged = (int) c.get(c.size()-flag+k);
for(int l = 0 ; l< row ; l++){
array[l][columnTOBeChanged] = 0;
}
}
}
display(array, row, col);
}
for(int i = 0 ; i<c.size() ; i++ ){
int colFetched = (int) c.get(i);
for(int j = 0 ; j < row ; j++){
array[j][colFetched]=0;
}
}
}
public static void display(int array[][], int row, int col){
System.out.println("\n\n");
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(array[i][j] + " ");
}
System.out.print("\n");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int row= 3;
int col = 3;
int[][] array1 = new int[row][col];
populate(array1,row,col);
display(array1,row,col);
trav(array1,row,col);
}
private static void populate(int[][] array,int row,int col) {
// TODO Auto-generated method stub
Random rand = new Random();
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
array[i][j]=rand.nextInt(col);
}
}
}
}
Here is the Java Code
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int[][] arr2D = new int[][]{{1, 2, 3}, {4, 0, 6}, {7, 8, 9},{10,11,12}};
int rid = -1, cid = -1;
System.out.println("The array is:");
for (int[] arr1D : arr2D) {
System.out.println();
for (int i : arr1D) {
System.out.print(" "+i);
}
}
//System.out.println("\nNumber of rows:"+arr2D.length);
for(int r = 0; r<arr2D.length; r++)
for(int c = 0; c<arr2D[r].length; c++ )
if(arr2D[r][c]==0){
rid = r;
cid = c;
break;
}
if((rid==-1) || (cid ==-1))
System.out.println("\nNo non zero element.");
else{
for(int c=0;c<arr2D[0].length;c++)
arr2D[rid][c] = 0;
for(int r=0;r<arr2D.length;r++)
arr2D[r][cid] = 0;
System.out.println("\nThe modified array is:");
for (int[] arr1D : arr2D) {
System.out.println();
for (int i : arr1D) {
System.out.print(" "+i);
}
}
}
}
}
public class Question {
public static void nullifyRow(int[][] matrix, int row) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[row][j] = 0;
}
}
public static void nullifyColumn(int[][] matrix, int col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
public static void setZeros2(int[][] matrix) {
boolean rowHasZero = false;
boolean colHasZero = false;
// Check if first row has a zero
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
rowHasZero = true;
break;
}
}
// Check if first column has a zero
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
colHasZero = true;
break;
}
}
// Check for zeros in the rest of the array
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length;j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Nullify rows based on values in first column
for (int i = 1; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
nullifyRow(matrix, i);
}
}
// Nullify columns based on values in first row
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
nullifyColumn(matrix, j);
}
}
// Nullify first row
if (rowHasZero) {
nullifyRow(matrix, 0);
}
// Nullify first column
if (colHasZero) {
nullifyColumn(matrix, 0);
}
}
public static void setZeros(int[][] matrix) {
boolean[] row = new boolean[matrix.length];
boolean[] column = new boolean[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length;j++) {
if (matrix[i][j] == 0) {
row[i] = true;
column[j] = true;
}
}
}
// Nullify rows
for (int i = 0; i < row.length; i++) {
if (row[i]) {
nullifyRow(matrix, i);
}
}
// Nullify columns
for (int j = 0; j < column.length; j++) {
if (column[j]) {
nullifyColumn(matrix, j);
}
}
}
public static boolean matricesAreEqual(int[][] m1, int[][] m2) {
if (m1.length != m2.length || m1[0].length != m2[0].length) {
return false;
}
for (int k = 0; k < m1.length; k++) {
for (int j = 0; j < m1[0].length; j++) {
if (m1[k][j] != m2[k][j]) {
return false;
}
}
}
return true;
}
public static int[][] cloneMatrix(int[][] matrix) {
int[][] c = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
c[i][j] = matrix[i][j];
}
}
return c;
}
public static void main(String[] args) {
int nrows = 10;
int ncols = 15;
int[][] matrix1 = AssortedMethods.randomMatrix(nrows, ncols, 0, 100);
int[][] matrix2 = cloneMatrix(matrix1);
AssortedMethods.printMatrix(matrix1);
setZeros(matrix1);
setZeros2(matrix2);
System.out.println();
AssortedMethods.printMatrix(matrix1);
System.out.println();
AssortedMethods.printMatrix(matrix2);
if (matricesAreEqual(matrix1, matrix2)) {
System.out.println("Equal");
} else {
System.out.println("Not Equal");
}
}
}
Assorted Method.randomMatrix is simple function to print Matrix
public static int[][] randomMatrix(int M, int N, int min, int max) {
int[][] matrix = new int[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
matrix[i][j] = randomIntInRange(min, max);
}
}
return matrix;
}
import CtCILibrary.AssortedMethods;
public class Question {
public static void nullifyRow(int[][] matrix, int row) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[row][j] = 0;
}
}
public static void nullifyColumn(int[][] matrix, int col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
public static void setZeros2(int[][] matrix) {
boolean rowHasZero = false;
boolean colHasZero = false;
// Check if first row has a zero
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
rowHasZero = true;
break;
}
}
// Check if first column has a zero
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
colHasZero = true;
break;
}
}
// Check for zeros in the rest of the array
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length;j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Nullify rows based on values in first column
for (int i = 1; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
nullifyRow(matrix, i);
}
}
// Nullify columns based on values in first row
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
nullifyColumn(matrix, j);
}
}
// Nullify first row
if (rowHasZero) {
nullifyRow(matrix, 0);
}
// Nullify first column
if (colHasZero) {
nullifyColumn(matrix, 0);
}
}
public static void setZeros(int[][] matrix) {
boolean[] row = new boolean[matrix.length];
boolean[] column = new boolean[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length;j++) {
if (matrix[i][j] == 0) {
row[i] = true;
column[j] = true;
}
}
}
// Nullify rows
for (int i = 0; i < row.length; i++) {
if (row[i]) {
nullifyRow(matrix, i);
}
}
// Nullify columns
for (int j = 0; j < column.length; j++) {
if (column[j]) {
nullifyColumn(matrix, j);
}
}
}
public static boolean matricesAreEqual(int[][] m1, int[][] m2) {
if (m1.length != m2.length || m1[0].length != m2[0].length) {
return false;
}
for (int k = 0; k < m1.length; k++) {
for (int j = 0; j < m1[0].length; j++) {
if (m1[k][j] != m2[k][j]) {
return false;
}
}
}
return true;
}
public static int[][] cloneMatrix(int[][] matrix) {
int[][] c = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
c[i][j] = matrix[i][j];
}
}
return c;
}
public static void main(String[] args) {
int nrows = 10;
int ncols = 15;
int[][] matrix1 = AssortedMethods.randomMatrix(nrows, ncols, 0, 100);
int[][] matrix2 = cloneMatrix(matrix1);
AssortedMethods.printMatrix(matrix1);
setZeros(matrix1);
setZeros2(matrix2);
System.out.println();
AssortedMethods.printMatrix(matrix1);
System.out.println();
AssortedMethods.printMatrix(matrix2);
if (matricesAreEqual(matrix1, matrix2)) {
System.out.println("Equal");
} else {
System.out.println("Not Equal");
}
}
}
AssortedMethods.randomMatrix is a simple function to print matrix
public static int[][] randomMatrix(int M, int N, int min, int max) {
int[][] matrix = new int[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
matrix[i][j] = randomIntInRange(min, max);
}
}
return matrix;
}
void findZero(int[][] array){
for(int i=0;i<array.length;i++){
for (int j = 0; j < array[i].length; j++) {
if(array[i][j]==0){
for (int j2 = 0; j2 < array.length; j2++) {
array[i][j2]=0;
array[j2][j]=0;
}
break;
}
}
}
//result
for(int i=0;i<array.length;i++){
for (int j = 0; j < array[i].length; j++) {
System.out.println("array["+i+"]["+j+"]:"+array[i][j]);
}
}
}
public static void main(String[] args) {
int col = 0, row = 0;
int arr[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 0, 11 },
{ 12, 13, 14, 15 } };
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if (arr[i][j] == 0) {
col = i;
row = i;
}
}
}
for (int i = 0; i < 4; i++) {
arr[col][i] = 0;
arr[i][row] = 0;
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
#include <iostream.h>
#include <conio.h>
void main()
{
clrscr();
int a[3][3],b[10],k=0,z,i;
for(int p=0;p<10;p++)
b[p]=-1;
cout<<"Enter the aaray";
for(i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cin>>a[i][j];
if(a[i][j]==0)
{
b[k]=i;
k++;
b[k]=j;
k++;
}
}
}
for(i=0;i<10;i++)
{
if(b[i]!=-1)
{
z=b[i];
if(i%2==0)
{
for(int d=0;d<3;d++)
a[z][d]=0;
}
else
{
for(int d=0;d<3;d++)
a[d][z]=0;
}
}
}
for(i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cout<<a[i][j]<<"\t";
}
cout<<"\n";
}
getch();
}
#include <iostream.h>
#include <conio.h>
void main()
{
clrscr();
int a[3][3],b[10],k=0,z,i;
for(int p=0;p<10;p++)
b[p]=-1;
cout<<"Enter the aaray";
for(i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cin>>a[i][j];
if(a[i][j]==0)
{
b[k]=i;
k++;
b[k]=j;
k++;
}
}
}
for(i=0;i<10;i++)
{
if(b[i]!=-1)
{
z=b[i];
if(i%2==0)
{
for(int d=0;d<3;d++)
a[z][d]=0;
}
else
{
for(int d=0;d<3;d++)
a[d][z]=0;
}
}
}
for(i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cout<<a[i][j]<<"\t";
}
cout<<"\n";
}
getch();
}
#include <iostream.h>
#include <conio.h>
void main()
{
clrscr();
int a[3][3],b[10],k=0,z,i;
for(int p=0;p<10;p++)
b[p]=-1;
cout<<"Enter the aaray";
for(i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cin>>a[i][j];
if(a[i][j]==0)
{
b[k]=i;
k++;
b[k]=j;
k++;
}
}
}
for(i=0;i<10;i++)
{
if(b[i]!=-1)
{
z=b[i];
if(i%2==0)
{
for(int d=0;d<3;d++)
a[z][d]=0;
}
else
{
for(int d=0;d<3;d++)
a[d][z]=0;
}
}
}
for(i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cout<<a[i][j]<<"\t";
}
cout<<"\n";
}
getch();
}
#include<iostream>
#include<vector>
#include<set>
using namespace std;
int main()
{
int array[4][4] = {{1,2,3,4},
{5,6,7,8},
{9,10,0,12},
{13,0,15,16}};
int R=4; int C=4;
set<int> s1;
set<int> s2;
for( int i = 0 ;i < R ; i++ )
{
for(int j = 0; j < C;j++)
{
if( array[i][j] == 0 )
{
s1.insert(i);
s2.insert(j);
}
}
}
std::set<int>::iterator it;
for( it = s1.begin(); it != s1.end(); it++ )
{
for( int i = 0 ; i < C ; i++ )
{
array[*it][i] = 0;
}
} cout << endl;
for( it = s2.begin(); it != s2.end(); it++ )
{
for( int i = 0 ; i < R ; i++ )
{
array[i][*it] = 0;
}
}
for(int i = 0; i < R; i++)
{
for(int j = 0 ;j<C;j++)
{
cout << array[i][j] << " ";
} cout << endl;
}
}
#include<iostream>
#include<vector>
#include<set>
using namespace std;
int main()
{
int array[4][4] = {{1,2,3,4},
{5,6,7,8},
{9,10,0,12},
{13,0,15,16}};
int R=4; int C=4;
set<int> s1;
set<int> s2;
for( int i = 0 ;i < R ; i++ )
{
for(int j = 0; j < C;j++)
{
if( array[i][j] == 0 )
{
s1.insert(i);
s2.insert(j);
}
}
}
std::set<int>::iterator it;
for( it = s1.begin(); it != s1.end(); it++ )
{
for( int i = 0 ; i < C ; i++ )
{
array[*it][i] = 0;
}
} cout << endl;
for( it = s2.begin(); it != s2.end(); it++ )
{
for( int i = 0 ; i < R ; i++ )
{
array[i][*it] = 0;
}
}
for(int i = 0; i < R; i++)
{
for(int j = 0 ;j<C;j++)
{
cout << array[i][j] << " ";
} cout << endl;
}
}
import java.util.ArrayList;
public class Matrix {
public static int[][] setZeroRowsCols(int[][] matrix){
int len = matrix.length;
ArrayList<Pair> locations = new ArrayList<Pair>();
for(int i=0; i<len; i++){
for(int j=0; j<matrix[i].length; j++){
if(matrix[i][j]==0){
locations.add(new Pair(i,j));
}
}
}
for(Pair pair : locations){
int iPos = pair.iPos;
int jPos = pair.jPos;
for(int i=0; i<len; i++){
matrix[i][jPos]=0;
}
for(int j=0; j<matrix[iPos].length; j++){
matrix[iPos][j]=0;
}
}
return matrix;
}
private static void printMatrix(int[][] matrix) {
int len = matrix.length;
for(int i=0; i<len; i++){
for(int j=0; j<matrix[i].length; j++){
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}
static class Pair{
int iPos;
int jPos;
public Pair(int i, int j){
this.iPos = i;
this.jPos = j;
}
public Pair(){}
}
public static void main(String[] args){
int[][] matrix = {
{1,2,3,4},
{5,6,7,8},
{9,10,0,11},
{12,13,14,15}
};
System.out.println("Input:");
printMatrix(matrix);
matrix = setZeroRowsCols(matrix);
System.out.println("Output:");
printMatrix(matrix);
}
}
It will take O(N) time complexity...
public class Class1 {
public Class1() {
super();
}
public static void main(String args[]){
int a[][] = {{1, 2 , 3 , 4 },{5 , 6 , 7 , 8},{9 , 10 , 0 , 11},{12 , 13 , 14 , 15}};
int row=0 , col =0;
for(int i=0;i<16;i++){
if(i%4==0 && i!=0){
row++;
}
if(a[row][i%4]==0){
System.out.println("Founded Element!!!"+row+(i%4));
col = i%4;
break;
}
}
for(int i=0 ; i<4;i++){
a[row][i]=0;
}
for(int i=0;i<4;i++){
a[i][col]=0;
}
row =0 ;
for(int i=0;i<16;i++){
if(i%4==0 && i!=0){
row++;
System.out.println();
}
System.out.print(a[row][(i%4)]+" ");
}
}
}
It will take O(N) time complexity...
public class Class1 {
public Class1() {
super();
}
public static void main(String args[]){
int a[][] = {{1, 2 , 3 , 4 },{5 , 6 , 7 , 8},{9 , 10 , 0 , 11},{12 , 13 , 14 , 15}};
int row=0 , col =0;
for(int i=0;i<16;i++){
if(i%4==0 && i!=0){
row++;
}
if(a[row][i%4]==0){
System.out.println("Founded Element!!!"+row+(i%4));
col = i%4;
break;
}
}
for(int i=0 ; i<4;i++){
a[row][i]=0;
}
for(int i=0;i<4;i++){
a[i][col]=0;
}
row =0 ;
for(int i=0;i<16;i++){
if(i%4==0 && i!=0){
row++;
System.out.println();
}
System.out.print(a[row][(i%4)]+" ");
}
}
}
This is a in-place replacement except the matrix is traversed twice. Time complexity is O(m x n) + O(m x n). We might need some space for storing the rows and columns that have Zeroes.
1. Find all the positions (X,Y) where the value is ZERO
2. Keep all X positions to rows set and Y positions to column set
3. If for any position in the matrix (X,Y) existing in the row set or column set respectively set as Zero or else keep it the same
Here's python version:
def fill_rows_columns_with_zeros(my_input):
x_dimensions = len(my_input)
y_dimensions = len(my_input[0])
zero_tuples = []
# First find places of elements which are 0s.
for x in range(x_dimensions):
for y in range(y_dimensions):
if my_input[x][y] != 0:
continue
zero_tuples.append((x, y))
# Set row and columns to be 0 for all found places:
for x, y in zero_tuples:
for z in range(0, y_dimensions):
my_input[x][z] = 0
for z in range(0, x_dimensions):
my_input[z][y] = 0
and some test code:
my_input = [[x, x + 1, x + 2, x + 3] for x in range(1, 17, 4)]; my_input[2][2] = 0;
for sublist in my_input: print sublist
fill_rows_columns_with_zeros(my_input)
for sublist in my_input: print sublist
This will work
public static void LoadArray()
{
ArrayList rowindicator = new ArrayList();
ArrayList columnindicator = new ArrayList();
int[,] array = new int[5, 5];
array[0, 0] = 1; array[0, 1] = 1; array[0, 2] = 1; array[0, 3] = 1; array[0, 4] = 1;
array[1, 0] = 1; array[1, 1] = 1; array[1, 2] = 1; array[1, 3] = 1; array[1, 4] = 1;
array[2, 0] = 0; array[2, 1] = 1; array[2, 2] = 0; array[2, 3] = 1; array[2, 4] = 0;
array[3, 0] = 1; array[3, 1] = 1; array[3, 2] = 1; array[3, 3] = 1; array[3, 4] = 1;
array[4, 0] = 1; array[4, 1] = 1; array[4, 2] = 1; array[4, 3] = 1; array[4, 4] = 0;
for (int i = 0; i < array.GetLength(0); i++)
{
for (int j = 0; j < array.GetLength(1); j++)
{
Console.Write(array[i, j]);
}
Console.WriteLine();
}
for (int i = 0; i < array.GetLength(0); i++)
{
for (int j = 0; j < array.GetLength(1); j++)
{
if (array[i, j] == 0)
{
// flagarray[i, j] = true;
rowindicator.Add(i);
columnindicator.Add(j);
}
}
Console.WriteLine();
}
for (int rowcount = 0; rowcount < rowindicator.Count; rowcount++)
{
for (int colcount = 0; colcount < array.GetLength(1); colcount++)
{
array[Convert.ToInt32(rowindicator[rowcount]), colcount] = 0;
}
}
for (int colcount = 0; colcount < columnindicator.Count; colcount++)
{
for (int rowcount = 0; rowcount < array.GetLength(0); rowcount++)
{
array[rowcount, Convert.ToInt32(columnindicator[colcount])] = 0;
}
}
for (int i = 0; i < array.GetLength(0); i++)
{
for (int j = 0; j < array.GetLength(1); j++)
{
Console.Write(array[i, j]);
}
Console.WriteLine();
}
}
my algorithm is O(m*n), which m,n is the length of row and col.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace RepZero
{
class Program
{
static List<List<int>> matrix = new List<List<int>>
{
new List<int> {1,2,3,4},
new List<int> {5,6,7,8},
new List<int> {9,10,0,12},
new List<int> {13,0,15,16}
};
static List<int> row = new List<int> { 1, 1, 1, 1 };
static List<int> col = new List<int> { 1, 1, 1, 1 };
static void Main(string[] args)
{
Console.WriteLine("row : ");
printList(row);
Console.WriteLine();
Console.WriteLine("col : ");
printList(col);
Console.WriteLine();
Console.WriteLine("matrix : ");
printMatrix(matrix);
Console.WriteLine();
Console.WriteLine("progress.");
findZero();
Console.WriteLine("row : ");
printList(row);
Console.WriteLine();
Console.WriteLine("col : ");
printList(col);
Console.WriteLine();
Console.WriteLine("replace Zero.");
replaceZero();
Console.WriteLine("matrix : ");
printMatrix(matrix);
Console.ReadKey();
}
static void findZero()
{
for (int r = 0; r < matrix.Count(); r++)
{
if (row[r] == 0) continue;
for (int c = 0; c < matrix[r].Count(); c++)
{
if (col[c] == 0) continue;
if (matrix[r][c] == 0)
{
row[r] = 0;
col[c] = 0;
}
}
}
}
static void replaceZero()
{
// update row
for (int r = 0; r < row.Count(); r++)
{
if (row[r] == 0)
{
for (int i = 0; i < matrix[r].Count(); i++)
{
matrix[r][i] = 0;
}
}
}
// update col
for (int c = 0; c < col.Count(); c++)
{
if (col[c] == 0)
{
for (int i = 0; i < matrix.Count(); i++)
{
matrix[i][c] = 0;
}
}
}
}
static void printList(List<int> list)
{
foreach (var item in list)
{
Console.Write(item + ",");
}
}
static void printMatrix(List<List<int>> matrix)
{
foreach (var row in matrix)
{
printList(row);
Console.WriteLine();
}
}
}
}
my algorithm is O(m*n), which m,n is the length of row and col.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace RepZero
{
class Program
{
static List<List<int>> matrix = new List<List<int>>
{
new List<int> {1,2,3,4},
new List<int> {5,6,7,8},
new List<int> {9,10,0,12},
new List<int> {13,0,15,16}
};
static List<int> row = new List<int> { 1, 1, 1, 1 };
static List<int> col = new List<int> { 1, 1, 1, 1 };
static void Main(string[] args)
{
Console.WriteLine("row : ");
printList(row);
Console.WriteLine();
Console.WriteLine("col : ");
printList(col);
Console.WriteLine();
Console.WriteLine("matrix : ");
printMatrix(matrix);
Console.WriteLine();
Console.WriteLine("progress.");
findZero();
Console.WriteLine("row : ");
printList(row);
Console.WriteLine();
Console.WriteLine("col : ");
printList(col);
Console.WriteLine();
Console.WriteLine("replace Zero.");
replaceZero();
Console.WriteLine("matrix : ");
printMatrix(matrix);
Console.ReadKey();
}
static void findZero()
{
for (int r = 0; r < matrix.Count(); r++)
{
if (row[r] == 0) continue;
for (int c = 0; c < matrix[r].Count(); c++)
{
if (col[c] == 0) continue;
if (matrix[r][c] == 0)
{
row[r] = 0;
col[c] = 0;
}
}
}
}
static void replaceZero()
{
// update row
for (int r = 0; r < row.Count(); r++)
{
if (row[r] == 0)
{
for (int i = 0; i < matrix[r].Count(); i++)
{
matrix[r][i] = 0;
}
}
}
// update col
for (int c = 0; c < col.Count(); c++)
{
if (col[c] == 0)
{
for (int i = 0; i < matrix.Count(); i++)
{
matrix[i][c] = 0;
}
}
}
}
static void printList(List<int> list)
{
foreach (var item in list)
{
Console.Write(item + ",");
}
}
static void printMatrix(List<List<int>> matrix)
{
foreach (var row in matrix)
{
printList(row);
Console.WriteLine();
}
}
}
}
Another way to do in it in C# since this is Microsoft interview.
public static void PrintZero(int[][] array)
{
var zeroLocations = FindZeroLocation(array);
for (int r = 0; r < array.Length; r++)
{
Console.WriteLine("");
for (int c = 0; c < array[r].Length; c++)
{
if (array[r][c] == 0)
Console.Write("0 ");
else if (zeroLocations[0].Contains(r))
Console.Write("0 ");
else if (zeroLocations[1].Contains(c))
Console.Write("0 ");
else
Console.Write(array[r][c] + " ");
}
}
}
public static List<HashSet<int>> FindZeroLocation(int[][] array)
{
var rowsIndex = new HashSet<int>();
var colIndex = new HashSet<int>();
var col = 0;
var row = 0;
foreach (int[] rows in array)
{
foreach (int num in rows)
{
if (num == 0)
{
rowsIndex.Add(row);
colIndex.Add(col);
}
col++;
}
row++;
col = 0;
}
var ZeroIndex = new List<HashSet<int>>();
ZeroIndex.Add(rowsIndex);
ZeroIndex.Add(colIndex);
return ZeroIndex;
}
The solution is simple. I am not writing the code but you can easily follow the logic to write your own.
We have to understand that as soon as we encounter an element as 0 in a row(or column), we can simply continue to the next row(or column).
1. Make 2 1-D boolean arrays for rows and columns. Mark all as false.
2. Go through the 2D array and mark the row number/column number as true and move to the next loop without checking any further in same row or column.
3. Go through the row array and mark all rows in matrix with boolean value true as 0.
4. Go through the column array and mark all columns with boolean value true as 0.
The solution is simple. I am not writing the code but you can easily follow the logic to write your own.
We have to understand that as soon as we encounter an element as 0 in a row(or column), we can simply continue to the next row(or column).
1. Make 2 1-D boolean arrays for rows and columns. Mark all as false.
2. Go through the 2D array and mark the row number/column number as true and move to the next loop without checking any further in same row or column.
3. Go through the row array and mark all rows in matrix with boolean value true as 0.
4. Go through the column array and mark all columns with boolean value true as 0.
$arr = array
(
array(1,2,2,2),
array(2,2,0,1),
array(3,0,3,2),
array(4,5,4,5)
);
for( $i=1; $i<count($arr); $i++ ) {
for( $j=1; $j<count($arr[$i]); $j++ ) {
if( 0 == $arr[$i][$j] ) {
$results[$i][$j] = 1;
}
}
}
foreach( $results as $key => $result ) {
for($j=0;$j<count($arr[$key]);$j++ ) {
$arr[$key][$j] = 0;
}
for($j=0;$j<count($arr);$j++ ) {
foreach($result as $column => $res ) {
$arr[$j][$column] = 0;
}
}
}
print_r($arr);
public static void MatrixAlter()
{
int[,] givenArray = new int[,] { { 1, 1, 2 }, { 0, 4, 1 }, { 5, 6, 1 } };
int rIndex = 0;
for (int i = 0; i < 3; i++)
{
int flag = 0;
int col = 0;
for (int j = 0; j < 3; j++)
{
if (givenArray[i, j] == 0)
{
col = j;
flag = 1;
givenArray[i, j] = -1;
j = 0;
}
if (flag == 1)
{
givenArray[i, j] = -1;
givenArray[j, col] = -1;
}
}
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (givenArray[i, j] == -1)
{
givenArray[i, j] = 0;
}
}
Console.WriteLine();
}
public static void MatrixAlter()
{
int[,] givenArray = new int[,] { { 1, 1, 2 }, { 0, 4, 1 }, { 5, 6, 1 } };
int rIndex = 0;
for (int i = 0; i < 3; i++)
{
int flag = 0;
int col = 0;
for (int j = 0; j < 3; j++)
{
if (givenArray[i, j] == 0)
{
col = j;
flag = 1;
givenArray[i, j] = -1;
j = 0;
}
if (flag == 1)
{
givenArray[i, j] = -1;
givenArray[j, col] = -1;
}
}
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (givenArray[i, j] == -1)
{
givenArray[i, j] = 0;
}
}
Console.WriteLine();
}
#include <stdio.h>
#include <stdlib.h>
struct coor{
int r;
int c;
};
void makeZero(int row, int col, int arr[row][col]){
int i,j,size=0;
struct coor *store=(struct coor*)malloc(sizeof(struct coor));
printf("Test Matrix\n");
for(i=0;i<row;i++){
for(j=0;j<col;j++){
printf(" %3d",arr[i][j]);
if(arr[i][j]==0){
store[size].r=i;
store[size].c=j;
size++;
store = (struct coor*)realloc(store,sizeof(struct coor)*(size+1));
}
}
printf("\n");
}
store[size].r=-1;
store[size].c=-1;
for(i=0;i<=size;i++)
printf("r = %d, c = %d\n",store[i].r,store[i].c);
for(i=0;i<size;i++){
memset(arr[store[i].r],0,col*sizeof(int));
for(j=0;j<row;j++)
arr[j][store[i].c]=0;
}
for(i=0;i<row;i++){
for(j=0;j<col;j++)
printf(" %3d",arr[i][j]);
printf("\n");
}
}
int main(void) {
int arr[4][5] = {
{1,0,3,4,6},
{5,1,7,5,5},
{9,8,6,0,6},
{1,2,3,4,5},
};
int row = sizeof(arr)/sizeof(arr[0]);
int col = sizeof(arr[0])/sizeof(int);
makeZero(row,col,arr);
return 0;
}
#include<iostream>
using namespace std;
int main()
{
int a[20][20],row,col,i,j,flag,k,l;
cin>>row>>col;
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
cin>>a[i][j];
}
flag=0;
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(a[i][j]==0)
{
flag=1;
k=i;
l=j;
break;
}
}
}
if(flag==1)
{
for(i=0;i<row;i++)
{
a[i][l]=0;
}
for(j=0;j<col;j++)
{
a[k][j]=0;
}
}
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
cout<<a[i][j]<<"\t";
}
cout<<"\n\n";
}
return 0;
}
package Matrix;
import java.util.Scanner;
public class FindZeroAndReplaceEntireRowAndCol {
public static int[][] findAndReplace(int[][] matrix, boolean[][] bmatrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0 && bmatrix[i][j]!=true) {
for (int j2 = 0; j2 < matrix[0].length; j2++) {
matrix[i][j2] = 0;
bmatrix[i][j2]=true;
}
for (int j2 = 0; j2 < matrix.length; j2++) {
matrix[j2][j] = 0;
bmatrix[j2][j]=true;
}
}
}
}
return matrix;
}
public static void display(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of row");
int row = sc.nextInt();
System.out.println("Enter the size of col");
int col = sc.nextInt();
int[][] matrix = new int[row][col];
System.out.println("Enter the elements of matrix");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[i][j] = sc.nextInt();
}
}
boolean[][] bmatrix = new boolean[row][col];
System.out.println("After finding zero and replacing the column and row");
display(findAndReplace(matrix, bmatrix));
}
}
package Matrix;
import java.util.Scanner;
public class FindZeroAndReplaceEntireRowAndCol {
public static int[][] findAndReplace(int[][] matrix, boolean[][] bmatrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0 && bmatrix[i][j]!=true) {
for (int j2 = 0; j2 < matrix[0].length; j2++) {
matrix[i][j2] = 0;
bmatrix[i][j2]=true;
}
for (int j2 = 0; j2 < matrix.length; j2++) {
matrix[j2][j] = 0;
bmatrix[j2][j]=true;
}
}
}
}
return matrix;
}
public static void display(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of row");
int row = sc.nextInt();
System.out.println("Enter the size of col");
int col = sc.nextInt();
int[][] matrix = new int[row][col];
System.out.println("Enter the elements of matrix");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[i][j] = sc.nextInt();
}
}
boolean[][] bmatrix = new boolean[row][col];
System.out.println("After finding zero and replacing the column and row");
display(findAndReplace(matrix, bmatrix));
}
}
package Matrix;
import java.util.Scanner;
public class FindZeroAndReplaceEntireRowAndCol {
public static int[][] findAndReplace(int[][] matrix, boolean[][] bmatrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0 && bmatrix[i][j]!=true) {
for (int j2 = 0; j2 < matrix[0].length; j2++) {
matrix[i][j2] = 0;
bmatrix[i][j2]=true;
}
for (int j2 = 0; j2 < matrix.length; j2++) {
matrix[j2][j] = 0;
bmatrix[j2][j]=true;
}
}
}
}
return matrix;
}
public static void display(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.print(matrix[i][j]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of row");
int row = sc.nextInt();
System.out.println("Enter the size of col");
int col = sc.nextInt();
int[][] matrix = new int[row][col];
System.out.println("Enter the elements of matrix");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[i][j] = sc.nextInt();
}
}
boolean[][] bmatrix = new boolean[row][col];
System.out.println("After finding zero and replacing the column and row");
display(findAndReplace(matrix, bmatrix));
}
}
In N X M Matrix, Consider N as row and M as column, need to optimize the below code.
O(n X m) for finding zeros and
In worst case O(n X m) for replacing the respective row and column with zeros, assuming if 1 entire row and entire column given as zeros.
E.g.
0 0 0
0 1 2
0 3 4
public static void ReplaceZeroRowsAndColumns()
{
StringBuilder strBlrdObj = new StringBuilder();
int[,] arrayElements = new int[4, 4];
int rowLength = arrayElements.GetLength(0);
int colLength = arrayElements.GetLength(1);
List<int> listOfZeroRows = new List<int>();
List<int> listOfZeroCols = new List<int>();
// Input.
for (int lpRCnt = 0; lpRCnt < rowLength; lpRCnt++)
{
for (int lpCCnt = 0; lpCCnt < colLength; lpCCnt++)
{
if (lpRCnt == 2 && (lpCCnt == 2))
{
arrayElements[lpRCnt, lpCCnt] = 0;
}
else
{
arrayElements[lpRCnt, lpCCnt] = ((lpRCnt+1)* (lpCCnt+1));
}
strBlrdObj.Append(arrayElements[lpRCnt, lpCCnt].ToString() + "\t");
}
strBlrdObj.Append("\n");
}
MessageBox.Show("Input Array:\n" + strBlrdObj.ToString());
// Actual Logic.
for (int lpRCnt = 0; lpRCnt < rowLength; lpRCnt++)
{
for (int lpCCnt = 0; lpCCnt < colLength; lpCCnt++)
{
if (arrayElements[lpRCnt, lpCCnt] == 0)
{
listOfZeroRows.Add(lpRCnt);
listOfZeroCols.Add(lpCCnt);
}
}
}
foreach (int row in listOfZeroRows)
{
for (int lpCCnt = 0; lpCCnt < colLength; lpCCnt++)
{
arrayElements[row, lpCCnt] = 0;
}
}
foreach (int col in listOfZeroCols)
{
for (int lpRCnt = 0; lpRCnt < rowLength; lpRCnt++)
{
arrayElements[lpRCnt, col] = 0;
}
}
//Output
for (int lpRCnt = 0; lpRCnt < rowLength; lpRCnt++)
{
for (int lpCCnt = 0; lpCCnt < colLength; lpCCnt++)
{
strBlrdObj.Append(arrayElements[lpRCnt, lpCCnt].ToString() + "\t");
}
strBlrdObj.Append("\n");
}
MessageBox.Show("\nOutput Array:\n" + strBlrdObj.ToString());
}
public static void replaceZero(int[][] array){
Set<Integer> rowList = new HashSet<Integer>();
Set<Integer> colList = new HashSet<Integer>();
for(int i=0;i<array.length;i++){
for(int j=0;j<array[i].length;j++){
if(array[i][j]==0){
colList.add(j);
rowList.add(i);
}
if(rowList.contains(i) || colList.contains(j)){
array[i][j]=0;
}
}
}
for(int i=0;i<array.length;i++){
for(int j=0;j<array[i].length;j++){
if(rowList.contains(i) || colList.contains(j)){
array[i][j]=0;
}
}
}
}
Time complexity O(n X m) is very high for best and average case.
if the matrix contains only one zero, we need to replace one row, one column.
In that scenario is it worth repeating loop for n rows X m columns.
I did some tweaking to handle all zeros in the matrix. Here is the code (tested)
int[,] array =
{
{0, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 0, 11},
{12, 13, 14, 15}
};
int[,] finalarray = new int[array.GetLength(0), array.GetLength(1)];
Array.Copy(array, 0,finalarray, 0,array.Length);
int row = 0;
int col = 0;
for (int i = 0; i < array.GetLength(0); i++)
{
for (int j = 0; j < array.GetLength(1); j++)
{
if (array[i, j] == 0)
{
for (int zerorow = 0; zerorow < array.GetLength(0); zerorow++)
{
for (int zerocol = 0; zerocol < array.GetLength(1); zerocol++)
{
if(zerorow == i)
finalarray[zerorow, zerocol] = 0;
if(j==zerocol)
finalarray[zerorow, zerocol] = 0;
}
}
row = i;
col = j;
}
}
}
private static void FillZeros(int[][] arr, int nRows, int nCols)
{
var rowsToZero = new bool[nRows];
var colsToZero = new bool[nCols];
for (int rowIdx = 0; rowIdx < nRows; rowIdx++)
for (int colIdx = 0; colIdx < nCols; colIdx++)
if (arr[rowIdx][colIdx] == 0)
{
rowsToZero[rowIdx] = true;
colsToZero[colIdx] = true;
}
for (int rowIdx = 0; rowIdx < nRows; rowIdx++)
for (int colIdx = 0; colIdx < nCols; colIdx++)
if (rowsToZero[rowIdx] || colsToZero[colIdx])
arr[rowIdx][colIdx] = 0;
}
public static void FindAndReplaceZero()
{
int[,] array =
{
{0, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 1, 11},
{12, 13, 14, 15}
};
int row = 0, col = 0;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (array[i, j] == 0)
{
row = i;
col = j;
}
}
}
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (j ==col )
{
array[i, j] = 0;
}
if (row == i)
{
array[i, j] = 0;
}
}
}
}
I think we can through the matrix first and find out all the zeros' cols and rows in it then fill those cols and rows.
But instead of scanning by row only or by col only, we can do it both in one loop, so the procedure is more like scanning the matrix from left up to right down, meanwhile we can record those to-be-filled cols and rows to save rebundant scannings.
import java.util.HashSet;
public class MatrixZero {
public static void findZeroFillRowCol(int[][] matrix){
int totalRow = matrix.length;
int totalCol = matrix[0].length;
HashSet<Integer> rowHasZero = new HashSet<Integer>();
HashSet<Integer> colHasZero = new HashSet<Integer>();
int row = 0, col = 0, i;
//scanning matrix
while(true){
if(row < totalRow){
if(!rowHasZero.contains(row)){
for(i = col; i < totalCol; ++i){
if(matrix[row][i] == 0){
rowHasZero.add(row);
colHasZero.add(i);
}
}
}
}
if(col < totalCol){
if(!colHasZero.contains(col)){
for(i = row; i < totalRow; ++i){
if(matrix[i][col] == 0){
colHasZero.add(col);
rowHasZero.add(i);
}
}
}
}
if(row + 1 == totalRow && col + 1 == totalCol) break;
if(row + 1 < totalRow) ++row;
if(col + 1 < totalCol) ++col;
}
//fill those rows and columns that contains zero
for(int r : rowHasZero){
for(i = 0; i < totalCol; ++i) matrix[r][i] = 0;
}
for(int c : colHasZero){
for(i = 0; i < totalRow; ++i) matrix[i][c] = 0;
}
}
public static void main(String[] args){
int[][][] array3d = {
{{0, 0, 0}, {0, 1, 2},{0, 3, 4}},
{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 0, 0, 1}, {2, 3, 4, 5}}
};
for(int[][] matrix : array3d){
findZeroFillRowCol(matrix);
for(int[] arr : matrix){
for(int i : arr) System.out.print(i + " ");
System.out.println();
}
}
}
}
-Initialize 2 arrays, countRows, countCols to zero, to keep track of which rows and columns to make zero.
-Scan the given matrix for zeros and make countRows[i] and countCols[j] = 1
-In the second pass, just go through countRows and countCols, look for 1 and make the corresponding row and column 0.
Complexity: O(m x n)
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int a[][] = { {1,2,3,4} , {5,6,7,8} , {9,0,11,12} , {13,14,15,16}, {17,18,0,20} };
a = repZeros(a);
for(int i=0; i<a.length;i++)
System.out.println(Arrays.toString(a[i]));
}
public static int[][] repZeros(int a[][]) {
int countRows[] = new int[a.length];
int countCols[] = new int[a[0].length];
for(int i=0; i<countRows.length; i++)
countRows[i] = 0;
for(int j=0; j<countCols.length; j++)
countRows[j] = 0;
for(int i = 0; i<a.length; i++) {
for(int j=0; j<a[0].length; j++) {
if(a[i][j] == 0) {
countRows[i] = 1;
countCols[j] = 1;
}
}
}
for(int i=0; i<countRows.length; i++) {
if(countRows[i] == 1) {
for(int j=0;j<countCols.length; j++)
a[i][j] = 0;
}
}
for(int i=0; i<countCols.length; i++) {
if(countCols[i] == 1) {
for(int j=0;j<countRows.length; j++)
a[j][i] = 0;
}
}
return a;
}
}
Vishal,
Keeping 2 arrays (with fixed length) for counting zeros will perform poor in best case scenario.
E.g. If we consider only one zero exists in matrix we need to iterate only for 1 row and 1 colum but, from your example it will iterate n X m times and checks for 1 in the count array.
If we store in list or hashset, we can use foreach and iterate only for 1 row and 1 column in best case scenario. You can refer my answer.
This is not very optimized code. But this will work.
/*In given array find zero and replace the entire row and column with zeros
E.g Input:
1 2 3 4
5 6 7 8
9 10 0 11
12 13 14 15
Output:
1 2 0 4
5 6 0 8
0 0 0 0
12 13 0 15
*/
#include<stdio.h>
#include<conio.h>
#define row 4
#define col 3
main()
{
int i,j;
int m,n;
int arr[row][col];
printf("Inputing matrix...");
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
scanf("%d",&arr[i][j]);
}
}
printf("Matrix is..");
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(j%col==0)
{
printf("\n");
}
printf("%d\t ",arr[i][j]);
}
}
int flag=0;
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(arr[i][j]==0)
{
printf("\nZero is located at index (%d,%d)\n",i,j);
m=i;
n=j;
}
}
}
for(int k=0;k<col;k++)
{
arr[m][k]=0;
}
for(int l=0;l<row;l++)
{
arr[l][n]=0;
}
printf("\nModified Matrix...");
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(j%col==0)
{
printf("\n");
}
printf("%d\t ",arr[i][j]);
}
}
}
/*In given array find zero and replace the entire row and column with zeros
E.g Input:
1 2 3 4
5 6 7 8
9 10 0 11
12 13 14 15
Output:
1 2 0 4
5 6 0 8
0 0 0 0
12 13 0 15
*/
#include<stdio.h>
#include<conio.h>
#define row 4
#define col 3
main()
{
int i,j;
int m,n;
int arr[row][col];
printf("Inputing matrix...");
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
scanf("%d",&arr[i][j]);
}
}
printf("Matrix is..");
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(j%col==0)
{
printf("\n");
}
printf("%d\t ",arr[i][j]);
}
}
int flag=0;
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(arr[i][j]==0)
{
printf("\nZero is located at index (%d,%d)\n",i,j);
m=i;
n=j;
}
}
}
for(int k=0;k<col;k++)
{
arr[m][k]=0;
}
for(int l=0;l<row;l++)
{
arr[l][n]=0;
}
printf("\nModified Matrix...");
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(j%col==0)
{
printf("\n");
}
printf("%d\t ",arr[i][j]);
}
}
}
#include <stdio.h>
#include<string.h>
int main()
{
int i, j, x, y;
int a[3][3] = {1, 2,0 ,4,5, 6,7,8,9};
printf("\ncheck postion of zero");
for(i = 0; i < 3; i++)
{
for(j = 0; j < 3; j++)
{
if(a[i][j] == 0)
{
x = i;
y = j;
}
}
}
printf("\n Out put \n");
for(i = 0; i < 3; i++)
{
for(j = 0; j < 3; j++)
{
if(i == x | (j == y))
{
a[i][j] = 0;
}
printf("%d ", a[i][j]);
}
printf("\n");
}
return 0;
}
Pushpendra,
What happens if more than 1 zero given in the input array.
From your code x,y will get overwritten by the last zero position.
Refer the sample input given in my answer, though in question I have given only 1 zero.
Thanks,
Srigopal
#include<stdio.h>
void main()
{
int a[15][15],i,j,m,n,s;
printf("Enter row and column size: ");
scanf("%d%d",&m,&n);
printf("Enter elements:");
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf("Enter index:");
scanf("%d",&s);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]==s)
{
for(j=0;j<n;j++)
{
a[i][j]=0;
}
}
}
}
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
printf("%d,",a[i][j]);
}
}
Soumyarup,
What happens if more than 1 zero given in the same row or column (which you are referring as j) array.
From your code j is used for replacing the first zero cell in column or row, the next column or row will not be handled in this scenario.
Refer the sample input given in my answer, though in question I have given only 1 zero.
From your program.
If input is
1 2 3 4
5 6 7 8
9 0 0 1
2 3 4 5
Output :
1 0 3 4
5 0 7 8
0 0 0 0
2 0 4 5
3,7,4 also should get replaced with zero.
Thanks,
Srigopal
public static void replaceRowNcolumWith0(){
int matricArray[][] = new int[][]{{1,2,3,5},{5,6,0,43},{9,10,11,6},{13,14,15,8},{1}};
int row = 0,col = 0; // A element's row number and column number which is 0.
for(int i=0;i<matricArray.length;i++){ // find where exactly is 0
for(int j=0;j<matricArray[i].length;j++){
System.out.print(matricArray[i][j]+" ");
if(matricArray[i][j] == 0){
row = i;
col = j;
}
}
System.out.println();
}
for(int k=0;k<matricArray.length;k++){ // replace row and column with 0
for(int l=0;l<matricArray[k].length;l++){
if(row==k || col==l)
matricArray[k][l] = 0;
}
}
for(int i=0;i<matricArray.length;i++){ // print matric
for(int j=0;j<matricArray[i].length;j++){
System.out.print(matricArray[i][j]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] a = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 0, 12 },
{ 12, 13, 14, 15 } };
int i = 0;
int j = 0;
boolean found = false;
for (i = 0; i < a.length; i++) {
for (j = 0; j < a[i].length; j++) {
if (a[i][j] == 0) {
found = true;
break;
}
}
if(found) {
break;
}
}
// Zero column j for all rows
for (int k = 0; k < a.length; k++) {
a[k][j] = 0;
}
print(a);
//Zero row i for all columns
for (int x = 0; x < a[i].length; x++) {
a[i][x] = 0;
}
print(a);
}
static void print(int[][] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
public static void replaceZero(int[][] array){
Set<Integer> rowList = new HashSet<Integer>();
Set<Integer> colList = new HashSet<Integer>();
for(int i=0;i<array.length;i++){
for(int j=0;j<array[i].length;j++){
if(array[i][j]==0){
rowList.add(i);
colList.add(j);
}
if(rowList.contains(i) || colList.contains(j)){
array[i][j]=0;
}
}
}
}
public static void replaceZero(int[][] array){
Set<Integer> rowList = new HashSet<Integer>();
Set<Integer> colList = new HashSet<Integer>();
for(int i=0;i<array.length;i++){
for(int j=0;j<array[i].length;j++){
if(array[i][j]==0){
rowList.add(i);
colList.add(j);
}
if(rowList.contains(i) || colList.contains(j)){
array[i][j]=0;
}
}
}
}
public static void replaceZero(int[][] array){
Set<Integer> colList = new HashSet<Integer>();
for(int i=0;i<array.length;i++){
boolean rowHas0 = false;
for(int j=0;j<array[i].length;j++){
if(array[i][j]==0){
colList.add(j);
rowHas0 = true;
}
else if(rowHas0 || colList.contains(j)){
array[i][j]=0;
}
}
}
}
- Vir Pratap Uttam May 10, 2015boolean[] row = new boolean[n]; boolean[] column = new boolean[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { row[i] = true; column[j] = true; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (row[i] || column[j]) { matrix[i][j] = 0; } } } System.out.println("Matrix After Setting zero:-"); printMatrix(matrix, n); return matrix; }