O(1) space in C


  • 1
    K

    My idea is simple, search for all zero in array, then process the zero entry one by one.

    To store the entry of zero, I use recursion to handle it.

    (I know it is not a good practice to use goto, but I am lazy to come up another way :) )

    void fill_zero(int **matrix, int target_row, int target_col, int row_size, int col_size)
    {
        int i;
        memset(matrix[target_row], 0, col_size * sizeof(int));
        for(i = 0; i < row_size; i++)
            matrix[i][target_col] = 0;
    }
    
    void _setZero(int** matrix, int matrixRowSize, int matrixColSize, int target_row, int target_col)
    {
        int i, j;
        // search if the same row has aother 0 entry
        for(j = target_col+1; j < matrixColSize; j++)
            if(matrix[target_row][j] == 0)
            {
                _setZero(matrix, matrixRowSize, matrixColSize, target_row, j);
                goto END;
            }
        
        for(i = target_row + 1; i < matrixRowSize; i++)
        {
            for(j = 0; j < matrixColSize; j++)
                if(matrix[i][j] == 0)
                {
                    _setZero(matrix, matrixRowSize, matrixColSize, i, j);
                    goto END;
                }
        }
    END:
        fill_zero(matrix, target_row, target_col, matrixRowSize, matrixColSize);
    }
    
    void setZeroes(int** matrix, int matrixRowSize, int matrixColSize)
    {
        int i, j;
        for(i = 0; i < matrixRowSize; i++)
            for(j = 0; j < matrixColSize; j++)
                if(matrix[i][j] == 0)
                {
                    _setZero(matrix, matrixRowSize, matrixColSize, i, j);
                    goto END;
                }
    END:{}
    }

  • 2
    J

    I think this is not what actually o(1), each time you call "_setZero", you are indeed using the storage system provided. So this is actually still o(m*n), but using a stack rather than an array.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.