[LeetCode] 73. Set Matrix Zeroes

https://leetcode.com/problems/set-matrix-zeroes/

Given amxnmatrix, if an element is 0, set its entire row and column to 0. Do itin-place.

• Example 1

      Input: 
      [
        [1,1,1],
        [1,0,1],
        [1,1,1]
      ]
      Output: 
      [
        [1,0,1],
        [0,0,0],
        [1,0,1]
      ]

• Example 2

      Input: 
      [
        [0,1,2,0],
        [3,4,5,2],
        [1,3,1,5]
      ]
      Output: 
      [
        [0,0,0,0],
        [0,4,5,0],
        [0,3,1,0]
      ]

Follow up

• 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

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean[] row = new boolean[matrix.length]; 
        boolean[] column = new boolean[matrix[0].length]; 

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    column[j] = true;
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (row[i] || column[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }   
}

1. 0이 있는 행, 혹은 열을 모두 0으로 세팅하면 되기 때문에
2. 어떤 열과 행에 0이 있는지 파악한 후 -> O(n)
3. 그 열과 행에 있는 모든 값을 0으로 변경한다 -> O(n)

• in-place : 새로운 배열을 만들지 않고, 그 배열 자체를 이용