Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
Solution: use vectors to count the rows and columns which need to be modified.
The following solution only use constant extra space (2 boolean variables). The key is to use the first row and the first column to store whether we should set the entire row/column to 0. Note that two boolean variables are required since we have to check whether the first row/column should be set to 0. These checks have to be done before we scanning the entire matrix; otherwise, the results might be overwritten.
Comments
Post a Comment