Set Matrix Zeros
Given an ‘N’ x ‘M’ integer matrix, if an element is 0, set its entire row and column to 0's, and return the matrix. In particular, your task is to modify it in such a way that if a cell has a value 0 (matrix[i][j] == 0), then all the cells of the ith row and jth column should be changed to 0.

You must do it in place.

For Example:

If the given grid is this: [7, 19, 3] [4, 21, 0] Then the modified grid will be: [7, 19, 0] [0, 0, 0]

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases. The first line of each test case contains two space-separated integers ‘N’ and ‘M’, denoting the no. of the rows and columns of the matrix. The next 'N' lines will contain ‘M’ space separated integers representing the elements of the matrix.

Output Format:

For each test case, print the modified grid. Print output of each test case in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 ≤ T ≤ 1000 1 ≤ m, n ≤ 1000 Σ(m * n) ≤ 2000000 -2^(31) ≤ matrix[i][j] ≤ 2^(31)-1, for all (1 ≤ i ≤ n and 1 ≤ j ≤ m). Time Limit: 1 sec

Follow up:

Can we do better than O(m * n) space? Using O(m + n) space is an improvement but we can still do better. We can do it using constant memory. Can you do it?

Question

Set Matrix Zeros

Given an ‘N’ x ‘M’ integer matrix, if an element is 0, set its entire row and column to 0's, and return the matrix. In particular, your task is to modify it in such a way that if a cell has a value 0 (matrix[i][j] == 0), then all the cells of the ith row and jth column should be changed to 0.

You must do it in place.

For Example:

If the given grid is this:
[7, 19, 3]
[4, 21, 0]

Then the modified grid will be:
[7, 19, 0]
[0, 0,  0]

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’, denoting the no. of the rows and columns of the matrix.

The next 'N' lines will contain ‘M’ space separated integers representing the elements of the matrix.

Output Format:

For each test case, print the modified grid.

Print output of each test case in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 ≤ T ≤ 1000
1 ≤ m, n ≤ 1000
Σ(m * n) ≤ 2000000
-2^(31) ≤ matrix[i][j] ≤ 2^(31)-1, for all (1 ≤ i ≤ n and 1 ≤ j ≤ m).

Time Limit: 1 sec

Follow up:

Can we do better than O(m * n) space?
Using O(m + n) space is an improvement but we can still do better.
We can do it using constant memory. Can you do it?

Accepted Answer

Brute-Force Approach

The basic idea is to maintain another boolean matrix ‘isZero’ which stores whether our resultant matrix should contain a zero at a particular index or not. We can traverse every element of our original matrix. If the element is 0, then we traverse the complete row and complete column of that particular element and set isZero values accordingly to true for all the elements in that row and column.

Algorithm:

setZeros(matrix)

Store dimensions of the matrix in n and m
Declare “isZero” boolean matrix of size n x m.
Iterate over i from 0 to n
- Iterate over j from 0 to m
  - If matrix[i][j] == 0
    - Iterate over k from 0 to n
      - Set isZero[k][j] = true
    - Iterate over k from 0 to m
      - Set isZero[i][k] = true
Iterate over i from 0 to n
- Iterate over j from 0 to m
  - If isZero[i][j] == true
    - Set matrix[i][j] = 0

Space Complexity: O(n^2)Explanation:

O(N * M) where N & M are dimensions of the given matrix.

We need to declare a 2D boolean matrix of size n x m. So the total required space will be O(N * M).

Time Complexity: O(n^3)Explanation:

O(N * M * (M + N)) where N & M are dimensions of the given matrix.

We are traversing each element. For each element that is zero, we are traversing its complete row and column. So we have O(M * N) elements and for each element, we can traverse a row and a column in the worst case, i.e. O(M + N). So total complexity is O(M * N * (M + N).

Java (SE 1.8)

/*
    Time Complexity: O(N * M * (N + M)) 
    Space Complexity:O(N * M) 

    Where N & M are dimensions of the given matrix.
*/

public class Solution {

	public static void setZeros(int matrix[][]) {

		// Storing dimensions of matrix in n and m.
		int n = matrix.length;
		int m = matrix[0].length;

		// Declaring isZero boolean matrix.
		Boolean isZero[][] = new Boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				isZero[i][j] = false;
			}
		}

		// Traversing the original matrix.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {

				// If that element of the matrix is equal to 0.
				if (matrix[i][j] == 0) {

					// Traversing its complete column and setting all the isZero values to be true.
					for (int k = 0; k < n; k++) {
						isZero[k][j] = true;
					}

					// Traversing its complete row and setting all the isZero values to be true.
					for (int k = 0; k < m; k++) {
						isZero[i][k] = true;
					}
				}
			}
		}

		// Travrsing isZero and if isZero at an index is true then we replace that
		// element with zero in original matrix.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (isZero[i][j]) {
					matrix[i][j] = 0;
				}
			}
		}
	}
}

Python (3.5)

'''
    Time Complexity: O(N * M * (N + M)) 
    Space Complexity:O(N * M) 

    Where N & M are dimensions of the given matrix.
'''

from typing import List

def setZeros(matrix: List[List[int]]) -> None:

    # Storing dimensions of matrix in n and m.
    n = len(matrix)
    m = len(matrix[0])
	
    # Declaring isZero boolean matrix.
    isZero = [[False for _ in range(m)] for _ in range(n)]
	
	# Traversing the original matrix.
    for i in range(n):
        for j in range(m):
			
			# If that element of the matrix is equal to 0.
            if matrix[i][j] == 0:
				
				# Traversing its complete column and setting all the isZero values to be true.
                for k in range(n):
                    isZero[k][j] = True
				
				# Traversing its complete row and setting all the isZero values to be true.
                for k in range(m):
                    isZero[i][k] = True
	
	# Travrsing isZero and if isZero at an index is true then we replace that element with zero in original matrix.
    for i in range(n):
        for j in range(m):
            if isZero[i][j]:
                matrix[i][j] = 0

C++ (g++ 5.4)

/*
    Time Complexity: O(N * M * (N + M)) 
    Space Complexity:O(N * M) 

    Where N & M are dimensions of the given matrix.
*/

void setZeros(vector> &matrix)
{
	// Storing dimensions of matrix in n and m.
	int n = matrix.size();
	int m = matrix[0].size();
	
	// Declaring isZero boolean matrix.
	vector> isZero(n,vector(m));
	
	// Traversing the original matrix.
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			
			// If that element of the matrix is equal to 0.
			if(matrix[i][j] == 0) {
				
				// Traversing its complete column and setting all the isZero values to be true.
				for(int k = 0; k < n; k++) {
					isZero[k][j] = true;
				}
				
				// Traversing its complete row and setting all the isZero values to be true.
				for(int k = 0; k < m; k++) {
					isZero[i][k] = true;
				}
			}
		}
	}
	
	// Travrsing isZero and if isZero at an index is true then we replace that element with zero in original matrix.
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(isZero[i][j]) {
				matrix[i][j] = 0;
			}
		}
	}
}

Accepted Answer

Space saver

The basic idea is to keep track of each row and each column and maintain two boolean arrays ‘rowZero’ and ‘colZero’ to store whether a particular row should be filled with all zeros or not and similarly another one for columns. We traverse each element and if the element is equal to 0 in the original matrix then we set ‘rowZero’ of its row and ‘colZero’ of its column to true. We iterate over ‘rowZero’ and set all the elements of all the rows to zero whose ‘rowZero’ is true and the same with columns while iterating on ‘colZero’.

Algorithm:

setZeros(matrix)

Store dimensions of matrix in n and m.
Declare boolean arrays “rowZero” and “colZero” of size n and m respectively.
Iterate over i from 0 to n
- Iterate over j from 0 to m
  - If matrix[i][j] == 0
    - Set colZero[j] = true
    - Set rowZero[i] = true
Iterate over i from 0 to n
- Iterate over j from 0 to m
  - If rowZero[i] is true or colZero[j] is true
    - Set matrix[i][j] = 0

Space Complexity: O(n)Explanation:

O(N + M) where N & M are dimensions of the given matrix.

We have to store two boolean arrays “rowZero” and “colZero” of size N and M respectively. So total space required will be O(M) + O(N) = O(M + N).

Time Complexity: O(n^2)Explanation:

O(N * M) where N & M are dimensions of the given matrix.

We are iterating over our matrix two times. So total complexity will be O(M * N) + O(M * N)

= O(M * N).

Python (3.5)

'''
    Time Complexity: O(N * M) 
    Space Complexity: O(N + M) 

    Where N & M are dimensions of the given matrix.
'''

from typing import List

def setZeros(matrix: List[List[int]]) -> None:

	# Storing dimensions of matrix in n and m.
	n = len(matrix)
	m = len(matrix[0])
	
    # Declaring two boolean arrays colZero and rowZero.
	colZero = [False for _ in range(m)]
	rowZero = [False for _ in range(n)]
	
	# Traversing the original matrix and filling values for rowZero and colZero.
	for i in range(n):
		for j in range(m):
			if matrix[i][j] == 0:
				colZero[j] = True
				rowZero[i] = True
	
	# Traversing the original matrix and changing values of matrix according to rowZero and colZero.
	for i in range(n):
		for j in range(m):
			if rowZero[i] or colZero[j]:
				matrix[i][j] = 0

Java (SE 1.8)

/*
    Time Complexity: O(N * M) 
    Space Complexity: O(N + M) 

    Where N & M are dimensions of the given matrix.
*/

public class Solution {

	public static void setZeros(int matrix[][]) {

		// Storing dimensions of matrix in n and m.
		int n = matrix.length;
		int m = matrix[0].length;

		// Declaring two boolean arrays colZero and rowZero.
		Boolean colZero[] = new Boolean[m];
		Boolean rowZero[] = new Boolean[n];
		for (int i = 0; i < m; i++) {
			colZero[i] = false;
		}
		for (int i = 0; i < n; i++) {
			rowZero[i] = false;
		}

		// Traversing the original matrix and filling values for rowZero and calZero.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (matrix[i][j] == 0) {
					colZero[j] = rowZero[i] = true;
				}
			}
		}

		// Traversing the original matrix and changing values of matrix according to
		// rowZero and colZero.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (rowZero[i] || colZero[j]) {
					matrix[i][j] = 0;
				}
			}
		}
	}
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N * M) 
    Space Complexity: O(N + M) 

    Where N & M are dimensions of the given matrix.
*/

void setZeros(vector> &matrix)
{
	// Storing dimensions of matrix in n and m.
	int n = matrix.size();
	int m = matrix[0].size();
	
	// Declaring two boolean arrays colZero and rowZero.
	vector colZero(m), rowZero(n);
	
	// Traversing the original matrix and filling values for rowZero and calZero.
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(matrix[i][j] == 0) {
				colZero[j] = rowZero[i] = true;
			}
		}
	}
	
	// Traversing the original matrix and changing values of matrix according to rowZero and colZero.
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(rowZero[i] || colZero[j]) {
				matrix[i][j] = 0;
			}
		}
	}
}

Accepted Answer

Super Space saver

The basic idea is to store whether a complete row and complete column should be zero or not but instead of declaring extra memory for this purpose, we are using the first row and first column of the original matrix to store this information. We are using two independent variables to store these values for the first row and first column. So we only need constant space for those two variables. Like the last approach we first find out whether a row should or column should be filled with all zeros or not. And after that, the eligible rows and columns are filled with zeros.

Algorithm:

setZeros(matrix)

Store dimensions of the matrix in n and m.
Declare boolean variables “firstRowZero” and “firstColZero” and initialize them to false.
Traverse over the first row and if any of it is zero then set firstRowZero to true.
Traverse over the first column and if any of it is zero then set firstColZero to true.
Iterate over i from 1 to n
- Iterate over j from 1 to m
  - If matrix[i][j] == 0
    - Set matrix[i][0] = 0
    - Set matrix[0][j] = 0
Iterate over i from 1 to n
- Iterate over j from 1 to m
  - If matrix[i][0] == 0 or matrix[0][j] == 0
    - Set matrix[i][j] = 0
If “firstColZero” is true
- Iterate over i from 0 to n
  - Set matrix[i][0] = 0
If “firstColZero” is true
- Iterate over j from 0 to m
  - Set matrix[0][j] = 0

Space Complexity: O(1)Explanation:

O(1)

We have to store two boolean variables. So we need constant storage space. Hence space required will be O(1).

Time Complexity: O(n^2)Explanation:

O(N * M) where N & M are dimensions of the given matrix.

We are iterating over our matrix two times. So total complexity will be O(M * N) + O(M * N)

= O(M * N)

C++ (g++ 5.4)

/*
    Time Complexity: O(N * M) 
    Space Complexity:O(1) 

    Where N & M are dimensions of the given matrix.
*/

void setZeros(vector> &matrix)
{
	// Storing dimensions of matrix in n and m.
	int n = matrix.size();
	int m = matrix[0].size();
	
	// Declaring two boolean variables firstColZero and firstRowZero.
	bool firstColZero = false, firstRowZero = false;
	
	// Setting firstColZero to true if any element in first column is zero.
	for(int i = 0; i < n; i++) {
		if(matrix[i][0] == 0) {
			firstColZero = true;
			break;
		}
	}
	
	// Setting firstRowZero to true if any element in first row is zero.
	for(int j = 0; j < m; j++) {
		if(matrix[0][j] == 0) {
			firstRowZero = true;
			break;
		}
	}
	
	// Setting values for each row and column to be zero or not.
	for(int i = 1; i < n; i++) {
		for(int j = 1; j < m; j++) {
			if(matrix[i][j] == 0) {
				matrix[i][0] = matrix[0][j] = 0;
			}
		}
	}
	
	// If any element of first row is zero then that complete column should be zero and vice-versa.
	for(int i = 1; i < n; i++) {
		for(int j = 1; j < m; j++) {
			if(matrix[i][0] == 0 || matrix[0][j] == 0) {
				matrix[i][j] = 0;
			}
		}
	}
	
	// Setting first row to zero if firstRowZero is true.
	if(firstColZero) {
		for(int i = 0; i < n; i++) {
			matrix[i][0] = 0;
		}
	}
	
	// Setting first column to zero if firstColZero is true.
	if(firstRowZero) {
		for(int j = 0; j < m; j++) {
			matrix[0][j] = 0;
		}
	}
}

Python (3.5)

'''
    Time Complexity: O(N * M) 
    Space Complexity:O(1) 

    Where N & M are dimensions of the given matrix.
'''

from typing import List

def setZeros(matrix: List[List[int]]) -> None:

	# Storing dimensions of matrix in n and m.
    n = len(matrix)
    m = len(matrix[0])
	
    # Declaring two boolean variables firstColZero and firstRowZero.
    firstColZero = False
    firstRowZero = False
	
	# Setting firstColZero to true if any element in first column is zero.
    for i in range(n):
        if matrix[i][0] == 0:
            firstColZero = True
            break
	
	# Setting firstRowZero to true if any element in first row is zero.
    for j in range(m):
        if matrix[0][j] == 0:
            firstRowZero = True
            break
	
	# Setting values for each row and column to be zero or not.
    for i in range(1, n):
        for j in range(1, m):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
	
	# If any element of first row is zero then that complete column should be zero and vice-versa.
    for i in range(1, n):
        for j in range(1, m):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
	
	# Setting first row to zero if firstRowZero is true.
    if firstColZero:
        for i in range(n):
            matrix[i][0] = 0
	
	# Setting first column to zero if firstColZero is true.
    if firstRowZero:
        for j in range(m):
            matrix[0][j] = 0

Java (SE 1.8)

/*
    Time Complexity: O(N * M) 
    Space Complexity:O(1) 

    Where N & M are dimensions of the given matrix.
*/

public class Solution {

    public static void setZeros(int matrix[][]) {

        // Storing dimensions of matrix in n and m.
        int n = matrix.length;
        int m = matrix[0].length;

        // Declaring two boolean variables firstColZero and firstRowZero.
        Boolean firstColZero = false, firstRowZero = false;

        // Setting firstColZero to true if any element in first column is zero.
        for (int i = 0; i < n; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }

        // Setting firstRowZero to true if any element in first row is zero.
        for (int j = 0; j < m; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

        // Setting values for each row and column to be zero or not.
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        // If any element of first row is zero then that complete column should be zero
        // and vice-versa.
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Setting first row to zero if firstRowZero is true.
        if (firstColZero) {
            for (int i = 0; i < n; i++) {
                matrix[i][0] = 0;
            }
        }

        // Setting first column to zero if firstColZero is true.
        if (firstRowZero) {
            for (int j = 0; j < m; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}

Accepted Answer

    rows,cols = len(matrix),len(matrix[0])
    arr_rows,arr_cols = [False]*rows,[False]*cols
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 0:
                arr_rows[i] = True
                arr_cols[j] = True
    for i in range(rows):
        for j in range(cols):
            if arr_rows[i] or arr_cols[j]:
                matrix[i][j] = 0
    return matrix

Accepted Answer

rows,cols = len(matrix),len(matrix[0]) arr_rows,arr_cols = [False]*rows,[False]*cols for i in range(rows): for j in range(cols): if matrix[i][j] == 0: arr_rows[i] = True arr_cols[j] = True for i in range(rows): for j in range(cols): if arr_rows[i] or arr_cols[j]: matrix[i][j] = 0 return matrix

You must do it in place.

For Example:

Input Format:

Output Format:

Note:

Constraints:

Follow up:

Top ServiceNow Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in ServiceNow Software Engineer