This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 73. Matrix zero on LeetCode, medium difficulty.

Tag: “Simulation”

Given an m x n matrix, if one element is 0, set all elements in its row and column to 0. Use the “in place” algorithm.

Advanced:

  • An intuitive solution would be to use extra space for O(m∗n)O(m * n)O(m∗n), but this is not a good solution.
  • A simple improvement would be to use O(m + n)O(m + n)O(m + n) extra space, but this is still not the best solution.
  • Can you come up with a solution that only uses constant space?

Example 1:

Input: matrix = [,1,1 [1], [1, 1], [1,1,1]] output: [[1, 1], [0, 0], [1, 1]]Copy the code

Example 2:

Input: matrix = [,1,2,0 [0], [3,4,5,2], [1,3,1,5]] output: [,0,0,0 [0], [0,4,5,0], [0,3,1,0]]Copy the code

Tip:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • –
    2 31 2^{31}     <= matrix[i][j] <=
    2 31 2^{31}     – 1

preface

Because O(m∗n)O(M *n)O(m∗n) O(m*n)O(M ∗n) and O(M +n)O(m+ N)O(m+ N) space are very simple solutions, nothing more than “matrices of equal size” or “identifiers equal to the number of rows and columns” to record zero information.

This paper focuses on the O(1)O(1)O(1) space solution using the original matrix.

O(1) space solution

1. Use two variables (r0 & c0) to record whether “first row & first column” should be set to zero

2. Non-first row first column position

  • Store the reset information to the original matrix
  • According to the zeroing information, set the position of non-first row and first column to zero

3. Set “first row & first column” to zero using r0 & c0

Code:

class Solution {
    public void setZeroes(int[][] mat) {
        int m = mat.length, n = mat[0].length;

        // 1. Scan first Row and First column to check whether the first row and first column should be set to zero
        boolean r0 = false, c0 = false;
        for (int i = 0; i < m; i++) {
            if (mat[i][0] = =0) {
                r0 = true;
                break; }}for (int j = 0; j < n; j++) {
            if (mat[0][j] == 0) {
                c0 = true;
                break; }}// 2.1 Scan the position of "non-first row, first column". If zero is found, store the information to the "leftmost" and "top" of the row
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (mat[i][j] == 0) {
                    mat[i][0] = mat[0][j] = 0; }}}// 2.2 Set "non-first row, first column" to zero according to the zeroing information just recorded in "leftmost" and "top" cells
        for (int j = 1; j < n; j++) {
            if (mat[0][j] == 0) {
                for (int i = 1; i < m; i++) {
                    mat[i][j] = 0; }}}for (int i = 1; i < m; i++) {
            if (mat[i][0] = =0) {
                Arrays.fill(mat[i], 0); }}// 3. Set the first row and first column to zero based on the first row and first column information recorded at the beginning
        if (r0) for (int i = 0; i < m; i++) mat[i][0] = 0;
        if (c0) Arrays.fill(mat[0].0); }}Copy the code
  • Time complexity: O(n∗m)O(n*m)O(n∗m)
  • Space complexity: O(1)O(1)O(1)

The last

This is the no.73 of our “Brush through LeetCode” series. The series started on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.