This is an interview question: In a two dimensional array of size mxn, for each element which value is zero, set to zero the entire row and column where this element is located, and leave the rest of the elements untouched.
The way I could htink of was to iterate through each element in the array, and for each time I encounter a zero, I mark the entire row and column with zeros. But this is naive, please suggest any improvements.
If extra space allowed. Just maintain two arrays of flag.
One stands for row, another stands for column. All default values set to 1.
Scan your original matrix, assume you find a 0 at the row x and column y. Just set row[x] = 0; and column[y] = 0;
Then scan your matrix again
for ( int i = 0; i < height; ++i )
for ( int j = 0; j < width; ++j )
M[i][j] = M[i][j] * row[i] * column[j];
Then you get your matrix M changed
The complexity of your algorithm is quadratic. If the entire matrix is initially all zeros, you'll wipe every column n_rows times and every row n_columns times.
A better approach is to maintain booleans arrays of size m and n that indicate which rows and columns need zeroing. Walk through the elements of the matrix, filling the boolean arrays appropriately. When you're done, walk through the boolean arrays and zero-fill according to the values you find in them. This way, each element is zeroed-out at most twice.
if you zero as you go along you will clear out every row and column after the first you find. Simply find and record all the zeros before zeroing out the rows and columns. Alternately, create a copy of your 2d array and modify the second, while looking at the first for reference.
Extra space allowed ? If so , given mxn matrix, we maintain two bitmaps one of size m for rows to indicate when a row should be zeroed and similarly for columns. Bitmaps makes it very easy to check in O(1) whether a row or column in already set.
Pass 1: Optimized iteration of matrix , while iterating through the elements of the matrix looking for zeros, when we find a zero is position (i,j) , we can set the corresponding bits in the two bit maps and stop iterating that row for further elements. (after all we are zeroing the whole row and column).
Pass 2: Now we have the two bit maps, loop through them zeroing the rows and columns. If you want to make is very optimal (if zeroing is a costly operation) while zeroing elements in a row you can skip if the corresponding column bit is set, which gets eventually zeroed while walking through columns.
EDIT: You can do it in one pass with just having a bitmap for columns alone, while iterating through the matrix if you find a zero, set that entire row and column to zeros, set the column bitmap position, and continue with the next row. Skip the columns with bit set while iterating subsequent rows
package helloWorld;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public static int[][] myFunction(int[][] matrix) {
// find all rows and columns that contains zeros
// keep their indexes in hashMap
// loop over the matrix and check if you have row and column in your
// hashmap if yes make them zero, and also mark the row/column as
// already zeroed
Map<String, Boolean> map = new HashMap<String, Boolean>();
int length = matrix[0].length;
int heigth = matrix.length;
for (int i = 0; i < heigth; i++) {
for (int j = 0; j < length; j++) {
if (matrix[i][j] == 0) {
// mark and keep Row in Map
if (!map.containsKey("R" + i)) {
map.put("R" + i, false);
}
// mark and keep column in Map
if (!map.containsKey("C" + j)) {
map.put("C" + j, false);
}
}
}
}
for (int i = 0; i < length; i++) {
//check if row need to be zeroed and if yes zero it and Mark it
//as done
if (map.containsKey("R" + i) && !map.get("R" + i)) {
for (int j = 0; j < length; j++) {
matrix[i][j] = 0;
}
map.put("R" + i, true);
}
//check if column need to be zeroed and if yes zero it and Mark
//it as done
if (map.containsKey("C" + i) && !map.get("C" + i)) {
for (int j = 0; j < heigth; j++) {
matrix[j][i] = 0;
}
map.put("C" + i, true);
}
}
return matrix;
}
public static void main(String[] args) {
int[][] matrix = { { 1, 2, 0, 7, 6 }, { 1, 0, 8, 7, 5 }, { 1, 2, 1,
7,-1 }, { 1, 2, 3, 4, 0 } };
print(matrix);
System.out.println("#####################################");
matrix=myFunction(matrix);
print(matrix);
}
public static void print(int[][] matrix) {
int h = matrix.length;
int l = matrix[0].length;
for (int i = 0; i < h; i++) {
for (int j = 0; j < l; j++) {
System.out.print(" " + matrix[i][j] + " ");
}
System.out.println();
}
}
}
