If zero found in Matrix. make entire row & column zero

Question

Problem is - If in an MxN matrix, a zero is encountered, the entire row and entire column should be set to zero.

Example -

8 4 2
2 3 7
1 0 1
9 8 4

Should become:

8 0 2
2 0 7
0 0 0
9 0 4

I encountered this problem today and came up with a solution. I'm hoping for some feedback regarding the time/space complexity and how efficient my solution is :

Code -

 public static void zeroMatrix(int[][] arr1)
{
 ArrayList<Integer> coord = new ArrayList<>();
 int row = arr1.length; 
 int column = arr1[0].length;
 for(int i=0; i < row; i++)
 {
 for(int j=0; j < column; j++)
 {
 if(arr1[i][j]==0)
 { 
 coord.add((10*i) + j);
 } 
 }
 }
 for(int n : coord)
 {
 int j=n%10;
 int i=n/10; int k=0;
 int l=0;
 while(k<row)
 {
 arr1[k][j]=0;
 k++;
 }
 while(l<column)
 {
 arr1[i][l]=0;
 l++;
 }
 }
}

What I'm doing is:

1. Saving the coordinates of found zeroes in an ArrayList as a two digit integer.

2. Taking out ones and tens places from the stored list (which are the coordinates) and running a loop over the found zeroes only.

3. Then making the corresponding rows and columns 0

Answer 1

Implementation

You did it right that you first find the zero entries and only after that set the rows/columns to zero. However, you can come up with more cohesive and flexible code:

public static void zeroMatrix(final int[][] matrix) {
 findZeroEntries(matrix).forEach((p) -> { 
 setToZero(matrix, p.x, p.y); 
 });
}
private static List<Point> findZeroEntries(final int[][] matrix) {
 final int height = matrix.length; 
 final int width = matrix[0].length;
 final List<Point> zeroEntryList = new ArrayList<>();
 for (int y = 0; y < height; ++y) {
 for (int x = 0; x < width; ++x) {
 if (matrix[y][x] == 0) {
 zeroEntryList.add(new Point(x, y));
 }
 }
 }
 return zeroEntryList;
}
private static void setToZero(final int[][] matrix, 
 final int x, 
 final int y) {
 setRowToZero(matrix, y);
 setColumnToZero(matrix, x);
}
private static void setRowToZero(final int[][] matrix, final int y) {
 final int width = matrix[0].length;
 for (int x = 0; x < width; ++x) {
 matrix[y][x] = 0;
 }
}
private static void setColumnToZero(final int[][] matrix, final int x) {
 final int height = matrix.length;
 for (int y = 0; y < height; ++y) {
 matrix[y][x] = 0;
 }
}

Coding conventions

Braces

What comes to braces, the recommended way to write them is to put the opening brace ({) on the same row with the statement that belongs to it. Instead of

for (...) 
{
 ...
}

you should write

for (...) {
 ...
}

Spaces

For the sake of readability, you should have a single space character after each for and if, and a single space character before and after any binary operator. So instead of

for(int i=0; ...) {
 if(i==1) {
 }
}

you should have

for (int i = 0; ...) {
 if (i == 1) {
 ...
 }
}

Program to interface

Not that it makes much difference in your method, but usually the rule goes that people should program to an interface, and not to an implementation. So instead of

ArrayList<Integer> coord = new ArrayList<>();

you should write

List<Integer> coord = new ArrayList<>();

Naming

arr1 is not the best possible name. Why not use, say, matrix?

Also

int row = arr1.length; 
int column = arr1[0].length;

above I would have used the plural form:

int rows = arr1.length; 
int columns = arr1[0].length;

Zero entry coordinates

As @200_success mentioned, packing the coordinates the way you do is not a good idea.

Hope that helps.

• I'll add comments tomorrow: "What comes to braces, the recommended way to write them" sounds a little unfounded, here is one source to back that up. I think it is up to personal taste and prefer almann style.
• borb183: Thanks for your comprehensive suggestions! Will take them into account. However, I do agree with @I'll add comments tomorrow , for braces I prefer the almann style as it appears neater and aligned :)
• coderodde: OK, I admit it, the issue is a matter of style. :-)
• borb183: One more question - we have to create a class 'Point' using your implementation, right?
• coderodde: @borb183 No, it's here: docs.oracle.com/javase/8/docs/api/java/awt/Point.html

Answer 2

Storing an (i, j) pair as a two-digit number is a nasty hack. The code will break horribly if there are ten or more rows or columns. If you must do such a hack, you could pack two ints into a long:

ArrayList<Long> coord = new ArrayList<>();
...
coord.add(i << 32 | j);

Writing an IntPair class would be less hackish, though.

• borb183: You're correct. This was a brute force solution and I couldn't understand any better way to store coordinate without an additional class. Thanks for the suggestion !