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?
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

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 4 Trees and Graphs