0130-surrounded-regions.js

/**
 * https://leetcode.com/problems/surrounded-regions/
 * Time O(ROWS * COLS) | Space O(ROWS * COLS)
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
 var solve = function solve(board) {
    searchRows(board);/* Time O(ROWS * COLS) | Space O(ROWS * COLS) */
    searchCols(board);/* Time O(ROWS * COLS) | Space O(ROWS * COLS) */
    searchGrid(board);/* Time O(ROWS * COLS) | Space O(ROWS * COLS) */
}

var searchRows = (board) => {
    const [ rows, cols ] = [ board.length, board[0].length ];

    for (let row = 0; row < rows; row++) {      /* Time O(ROWS) */
        dfs(board, row, rows, 0, cols);         /* Space O(ROWS) */
        dfs(board, row, rows, (cols - 1), cols);/* Space O(ROWS) */
    }
}

var searchCols = (board) => {
    const [ rows, cols ] = [ board.length, board[0].length ];

    for (let col = 1; col < (cols - 1); col++) {/* Time O(COLS) */
        dfs(board, 0, rows, col, cols);         /* Space O(COLS) */
        dfs(board, (rows - 1), rows, col, cols);/* Space O(COLS) */
    }
}

var searchGrid = (board) => {
    const [ rows, cols ] = [ board.length, board[0].length ];

    for (let row = 0; row < rows; row++) {/* Time O(ROWS) */
        for (let col = 0; col < cols; col++) {/* Time O(COLS) */
            const isO = board[row][col] === 'O';
            if (isO) board[row][col] = 'X';

            const isStar = board[row][col] === '*';
            if (isStar) board[row][col] = 'O';
        }
    }
}

const dfs = (board, row, rows, col, cols) => {
    const isBaseCase = board[row][col] !== 'O';
    if (isBaseCase) return;

    board[row][col] = '*';

    for (const [ _row, _col ] of getNeighbors(row, rows, col, cols)) {
        dfs(board, _row, rows, _col, cols);/* Time O(HEIGHT) | Space O(HEIGHT) */
    }
}

var getNeighbors = (row, rows, col, cols) => [ [0, 1], [0, -1], [1, 0], [-1, 0] ]
    .map(([ _row, _col ]) => [ (row + _row), (col + _col)])
    .filter(([ _row, _col ]) => (0 <= _row) && (_row < rows) && (0 <= _col) && (_col < cols))


/**
 * https://leetcode.com/problems/surrounded-regions/
 * Time O(ROWS * COLS) | Space O(ROWS * COLS)
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
 var solve = function solve(board, queue = new Queue([])) {
    searchRows(board, queue);/* Time O(ROWS + COLS) | Space O(ROWS + COLS) */
    searchCols(board, queue);/* Time O(ROWS + COLS) | Space O(ROWS + COLS) */
    bfs(board, queue);       /* Time O(ROWS * COLS) | Space O(ROWS * COLS) */
    searchGrid(board);       /* Time O(ROWS * COLS) */
}

var searchRows = (board, queue) => {
    const [ rows, cols ] = [ board.length, board[0].length ]

    for (let row = 0; row < rows; row++) { /* Time O(ROWS) */
        queue.enqueue([ row, 0 ]);         /* Space O(ROWS) */
        queue.enqueue([ row, (cols - 1) ]);/* Space O(ROWS) */
    }
}

var searchCols = (board, queue) => {
    const [ rows, cols ] = [ board.length, board[0].length ]

    for (let col = 0; col < (cols - 1); col++) {/* Time O(COLS) */
        queue.enqueue([ 0, col ]);              /* Space O(COLS) */
        queue.enqueue([ (rows - 1), col ]);     /* Space O(COLS) */
    }
}

var bfs = (board, queue) => {
    const [ rows, cols ] = [ board.length, board[0].length ];

    while (!queue.isEmpty()) {
        for (let i = (queue.size() - 1); 0 <= i; i--) {/* Time O(WIDTH) */
            const [ row, col ] = queue.dequeue();

            const isBaseCase = board[row][col] !== 'O';
            if (isBaseCase) continue;

            board[row][col] = '*';

            for (const [ _row, _col ] of getNeighbors(row, rows, col, cols)) {
                queue.enqueue([ _row, _col ]);         /* Space O(WIDTH) */
            }
        }
    } 
}

var searchGrid = (board) => {
    const [ rows, cols ] = [ board.length, board[0].length ];

    for (let row = 0; row < rows; row++) {/* Time O(ROWS) */
        for (let col = 0; col < cols; col++) {/* Time O(COLS) */
            const isO = board[row][col] === 'O';
            if (isO) board[row][col] = 'X';

            const isStar = board[row][col] === '*';
            if (isStar) board[row][col] = 'O';
        }
    }
}