[leetcode #73] Set Matrix Zeroes

Problem

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's, and return the matrix.

You must do it in place.

Example 1:

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

Example 2:

Input: matrix = [[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]]

Constraints:

・ m == matrix.length
・ n == matrix[0].length
・ 1 <= m, n <= 200
・ -2³¹ <= matrix[i][j] <= 2³¹ - 1

Follow up:

・ A straightforward 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?

Idea

직관적으로 생각하면 쉽게 풀 수 있는 문제다. 처음에 matrix를 탐색하고 0인 rowIndex와 columnIndex를 저장한다. 이후 matrix를 재탐색하면서 0이었던 row index나 0이었던 column index가 나올 경우 matrix를 0으로 설정한다.

이렇게 하면 너무 쉬우니, 문제에서 Space Complexity를 O(1)로 해서 풀 수 있는 방법을 생각해보라고 한다. 0인 cell을 찾을 경우 이를 저장할 array를 따로 만들지 않고 index가 0인 row와 index가 0인 column을 이용할 수 있다. matrix를 탐색하고 나면 index 0인 row와 index 0인 column의 원래 값이 덮어쓰여지게 되므로, 0인 cell이 있었는지 저장할 수 있는 추가적인 flag가 필요하다. 알고리즘은 다음과 같다.

1. matrix를 탐색한다.
   a. column이 0인 cell이 0일 경우 index가 0인 column을 0으로 만들기 위한 flag를 설정한다.
   b. row가 i, column이 j인 cell이 0일 경우 matrix[i][0]와 matrix[0][j]를 0으로 설정한다.
2. matrix를 재탐색한다. matrix[i][0] 또는 matrix[0][j]가 0일 경우 matrix[i][j]를 0으로 설정한다.
3. matrix[0][0]가 0일 경우 첫번째 row에 있는 cell을 전부 0으로 설정한다.
4. flag가 설정되었을 경우 첫번째 column에 있는 cell을 전부 0으로 설정한다.

Solution

Time Complexity O(m * n)
Space Complexity O(m + n)

class Solution {
    public void setZeroes(int[][] matrix) {
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        boolean[] zeroRows = new boolean[rowLen];
        boolean[] zeroCols = new boolean[colLen];

        for (int i=0; i < rowLen; i++) {
            for (int j=0; j < colLen; j++) {
                if (matrix[i][j] == 0) {
                    zeroRows[i] = true;
                    zeroCols[j] = true;
                }
            }
        }

        for (int i=0; i < rowLen; i++)
            if (zeroRows[i])
                for (int j=0; j < colLen; j++)
                    matrix[i][j] = 0;

        for (int j=0; j < colLen; j++)
            if (zeroCols[j])
                for (int i=0; i < rowLen; i++)
                    matrix[i][j] = 0;

    }
}

Time Complexity O(m * n)
Space Complexity O(1)

class Solution {
    public void setZeroes(int[][] matrix) {
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        boolean isCol = false;

        for (int i=0; i < rowLen; i++) {
            if (matrix[i][0] == 0)
                isCol = true;

            for (int j=1; j < colLen; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        for (int i=1; i < rowLen; i++) {
            for (int j=1; j < colLen; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0)
                    matrix[i][j] = 0;
            }
        }

        if (matrix[0][0] == 0) {
            for (int j=0; j < colLen; j++)
                matrix[0][j] = 0;
        }

        if (isCol) {
            for (int i=0; i < rowLen; i++)
                matrix[i][0] = 0;
        }
    }
}

Reference

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