matrix_1.png

matrix_2.png

/**
* Abstract: find the anchor and zero out its associate row&col, during 
* which we collect the zero position when encountering one; after that 
* we search the remaining entries for new anchors(which might be 
* repeatedly enqueued).
*/
typedef enum Type {
    TypeCol = 1 << 1,
    TypeRow = 1 << 2,
    TypeRowCol = TypeCol | TypeRow
};
typedef struct QNodeStruct {
    int i, j;
    enum Type type;
    struct QNodeStruct *next;
}*QNode;

QNode QNodeCreate(int i, int j, enum Type type) {
    QNode x = (QNode)malloc(sizeof(*x));
    x->i = i;
    x->j = j;
    x->type = type;
    x->next = NULL;
    return x;
}

typedef struct QueueStruct {
    int count;
    QNode head, tail;
}*Queue;

Queue QueueCreate() {
    Queue queue = (Queue)malloc(sizeof(*queue));
    queue->count = 0;
    queue->tail = queue->head = NULL;
    return queue;
}

void QueueEnqueue(Queue queue, int i, int j, enum Type type) { 
    QNode head = QNodeCreate(i, j, type);
    if (queue->count == 0) {
        queue->head = queue->tail = head;
    } else {
        queue->head->next = head;
        queue->head = head;
    }
    queue->count++;
}

void QueueDequeue(Queue queue, int *i, int *j, enum Type *type) { 
    QNode tail = queue->tail;
    queue->tail = tail->next;
    queue->count--;
    *i = tail->i;
    *j = tail->j;
    *type = tail->type;
    free(tail);
}

bool QueueIsEmpty(Queue queue) { return queue->count == 0; }

void set_zero(int **matrix, int m, int n, int row, int col, enum Type type, Queue queue, bool *rows, bool *cols) {
    if ((type & TypeRow) && !(rows[row])) {
        rows[row] = true;
        for (int j = 0; j < col; j++) {
            if (matrix[row][j] == 0) {
                if (!(cols[j])) { QueueEnqueue(queue, row, j, TypeCol); }
            } else {
                matrix[row][j] = 0;
            }
        }
        for (int j = col + 1; j < n; j++) {
            if (matrix[row][j] == 0) {
                if (!(cols[j])) { QueueEnqueue(queue, row, j, TypeCol); }
            } else {
                matrix[row][j] = 0;
            }
        }
    }
    if ((type & TypeCol) && !(cols[col])) {
        cols[col] = true;
        for (int i = 0; i < row; i++) {
            if (matrix[i][col] == 0) {
                if (!(rows[i])) { QueueEnqueue(queue, i, col, TypeRow); }
            } else {
                matrix[i][col] = 0;
            }
        }
        for (int i = row + 1; i < m; i++) {
            if (matrix[i][col] == 0) {
                if (!(rows[i])) { QueueEnqueue(queue, i, col, TypeRow); }
            } else {
                matrix[i][col] = 0;
            }
        }
    }
}

void find_next_zero(int **matrix, int m, int n, int row, Queue queue, bool *rows, bool *cols) {
    for (int i = row; i < m; i++) {
        if (!(rows[i])) {
            for (int j = 0; j < n; j++) {
                if (!(cols[j]) && matrix[i][j] == 0) { 
                    QueueEnqueue(queue, i, j, TypeRowCol);
                    return;
                }
            }
        }
    }
}

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize, n = *matrixColSize, row, col;
    bool *rows = (bool*)malloc(m * sizeof(*rows)), *cols = (bool*)malloc(n * sizeof(*cols));
    for (int i = 0; i < m; i++) { rows[i] = false; }
    for (int j = 0; j < n; j++) { cols[j] = false; }
    enum Type type;
    Queue queue = QueueCreate();
    find_next_zero(matrix, m, n, 0, queue, rows, cols);

    while (!QueueIsEmpty(queue)) {
        QueueDequeue(queue, &row, &col, &type);
        set_zero(matrix, m, n, row, col, type, queue, rows, cols);
        if (type == TypeRowCol) { find_next_zero(matrix, m, n, row + 1, queue, rows, cols); }
    }
}