Set Matrix Zeroes
Given an mXn matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Problem description:
The problem wants you to develop some logic such that all the elements of a certain row and column need to be changed to 0 if that position (row, col)==0. And leave other row and column as it is. The given problem needs that approach in which time complexity if constant that is without any extra space involved during the algorithm.
Input:
Given T number of test cases, each test case consists of matrix size mXn, m lines contain n elements either 1 or 0.
Output:
Print the final matrix after setting zeroes according to the question rule.
Examples:
Input:
T=1
M=3,N=3
1 1 1
1 0 1
1 1 1
Output:
1 0 1
0 0 0
1 0 1
This problem asks you to solve in-place. It means you can only use constant extra space that is in O(1) space complexity.
We will use to boolean variable row and col variable which will be initially false. We will check each row and find if the first element of the given row is 0 or not. If 0 then we will assign row=true and break. Similarly, we will assign col variable with false initially and then we will make it true after checking it all column first elements.
Now, we will travel all elements for the matrix except first row and first column and check if the current element is 0 or not. If 0 then we will make the first element of that column and row as 0.
We will again iterate through all elements of the matrix except first column and first row and check if the current element's first element in that column or the first element in that row is zero or not, if zero then we will make the current element as 0.
Finally, if the row variable that we initially declare is true then we will make the first element of each row as 0, and if col variable is also true then we will make the first element of each col as 0.
Time Complexity for above approach in worst case is (n*m)
Space complexity for above approach in worst case is O(1)
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer