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?
This question is of medium difficulty, but it's actually not difficult. The only tricky part is understanding "col" and "row"—you absolutely must figure them out. It's best to write them down on a piece of paper.
The main approach is to focus on O(1) space:
- Check if there is a 0 in row 0 and column 0.
- Check all rows and columns; if any contain 0, set the first row/first column to 0.
- Check row 0 and column 0 respectively. If there is a 0, set the first row/column to 0.
- Use the previously checked row and column 0; if there are 0s, set the row/column to 0.
public class Solution { public void setZeroes(int[][] matrix) { int row = matrix.length; int col = matrix[0].length; boolean brow = false; boolean bcol = false; //check if first row for(int i=0;i This siteOriginal articleAll follow "Attribution-NonCommercial-ShareAlike 4.0 License (CC BY-NC-SA 4.0)Please retain the following annotations when sharing or adapting:
Original author:Jake Tao,source:"LeetCode – 73. Set Matrix Zeroes"
