Set Matrix Zeroes

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 10

• -100 <= matrix[i][j] <= 100

Solutions

Steps

1. Initialize two boolean arrays row and col: These arrays are used to keep track of which rows and columns have at least one zero. The size of row is the number of rows in the matrix, and the size of col is the number of columns.

2. Identify rows and columns that need to be set to zero: This is done by iterating over each element in the matrix. If an element is zero, the corresponding entries in the row and col arrays are set to true.

3. Set identified rows to zero: For each true entry in the row array, set all elements in that row of the matrix to zero.

4. Set identified columns to zero: Similarly, for each true entry in the col array, set all elements in that column of the matrix to zero.

public class Solution
{
    public void SetZeroes(int[][] matrix)
    {
        bool[] row = new bool[matrix.Length];
        bool[] col = new bool[matrix[0].Length];

        // Identify rows and columns that need to be set to zero
        for (int i = 0; i < matrix.Length; i++) //N*M Times
        {
            for (int j = 0; j < matrix[0].Length; j++)
            {
                if (matrix[i][j] == 0)
                {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        // Set identified rows to zero
        for (int i = 0; i < row.Length; i++)
        {
            if (row[i])
            {
                for (int j = 0; j < matrix[0].Length; j++)
                {
                    matrix[i][j] = 0;
                }
            }
        }

        // Set identified columns to zero
        for (int i = 0; i < col.Length; i++)
        {
            if (col[i])
            {
                for (int j = 0; j < matrix.Length; j++)
                {
                    matrix[j][i] = 0;
                }
            }
        }
    }

}

Complexity

Time complexity: O(N*M)

Space complexity: O(N+M)