Author: Ron

Categories
Array Dynamic Programming Leetcode

Unique Paths with Obstacles

let uniquePathsWithObstacles = function(obstacleGrid) {

    if (!obstacleGrid || !obstacleGrid.length) return 0;

    function markNextRowsAsZero(col) {
        for (let i = col; i < maxCol; i++) {
            obstacleGrid[0][i] = 0;
        }
    }
    function markNextColumnsAsZero(row) {
        for (let i = row; i < maxRow; i++) {
            obstacleGrid[i][0] = 0;
        }
    }

    let maxRow = obstacleGrid.length,
        maxCol = obstacleGrid[0].length,
        OBSTACLE = 1, VISITED = -1;

    // first block is obstacle return 0;
    if (obstacleGrid[0][0] === OBSTACLE) {
        return 0;
    }

    // mark all first rows as either 1 or zero
    for (let col = 0; col < maxCol;col++) {
        if (obstacleGrid[0][col] === OBSTACLE) {
            markNextRowsAsZero(col);
            break;
        }
        else {
            obstacleGrid[0][col] = 1;
        }
    }

    // mark all first columns as either 1 or zero
    for (let row = 1; row < maxRow;row++) {
        if (obstacleGrid[row][0] === OBSTACLE) {
            markNextColumnsAsZero(row);
            break;
        }
        else {
            obstacleGrid[row][0] = 1;
        }
    }

    for (let row = 1; row < maxRow;row++) {
        for (let col = 1; col < maxCol;col++) {
            if (obstacleGrid[row][col] === OBSTACLE) {
                obstacleGrid[row][col] = 0;
            }
            else {
                obstacleGrid[row][col] =
                    obstacleGrid[row - 1][col] +
                    obstacleGrid[row][col - 1];
            }

        }
    }

    return obstacleGrid[maxRow - 1][maxCol - 1];
};
Categories
Dynamic Programming Leetcode Loop

Unique Paths (Iterative)

let uniquePaths = function(m, n) {

    let getKey = (row, col) => `${row}${col}`;

    let cache = { }
    for (let row = 1; row <= m; row++) {
        for (let col = 1; col <= n; col++) {
            if (row === 1) {
                cache[getKey(row, col)] = 1;
            }
            else if (col === 1) {
                cache[getKey(row, col)] = 1;
            }
            else {
                cache[getKey(row, col)] = cache[getKey(row-1, col)] + cache[getKey(row, col - 1)];
            }
        }
    }

    return cache[getKey(m,n)];
};
Categories
Leetcode Recursion

Unique Paths (Recursion)

let uniquePaths = function(m, n) {
    let results = new Set();
    function getPath(row, col, path = '') {
        if (row >= m && col >= n) {
            results.add(path);
            return;
        }

        if (row === m) {
            // go right if at the bottom row
            getPath(row, col + 1, path + 'R');
        }
        else if (col === n) {
            // go down if at the end column
            getPath(row + 1, col, path + 'D');
        }
        else {
            // go down and go right
            getPath(row, col + 1, path + 'R');
            getPath(row + 1, col, path + 'D');
        }
    }

    getPath(1, 1, 'S');
    return results.size;
};
Categories
Array Dynamic Programming Leetcode

Minimum Path Sum (Iterative)

let minPathSum = function(grid) {

    if(!grid || !grid.length) return 0;

    let maxRow = grid.length, maxCol = grid[0].length;
    
    for (let row = 0; row < maxRow;row++) {
        for (let col = 0; col < maxCol;col++) {
            console.log(row, col);
            if (row === 0) {
                grid[row][col] = grid[row][col] + (grid[row][col - 1] || 0);
            }
            else if (col === 0) {
                grid[row][col] = grid[row][col] + grid[row - 1][col];
            } else {
                grid[row][col] = Math.min(
                    grid[row][col] + grid[row - 1][col], // top
                    grid[row][col] + grid[row][col - 1] // left
                );
            }
        }
    }
    return grid[maxRow - 1][maxCol - 1];
};
Categories
Leetcode Recursion

Minimum Path Sum (Recursion)

let minPathSum = function(grid) {

    if(!grid || !grid.length) return 0;

    let maxRow = grid.length, maxCol = grid[0].length;
    function sum(row, col, total, path = '') {
        const val = grid[row][col] + total; //?
        if (row === maxRow - 1 && col === maxCol - 1) {
            return val;
        } //?

        if (row === maxRow - 1) {
            return sum(row, col + 1, val);
        }
        else if (col === maxCol - 1) {
            return sum(row + 1, col, val);
        } else {
            const down = sum(row + 1, col, val);
            const right = sum(row, col + 1, val);
            return Math.min(down, right);
        }
    }

    return sum(0, 0, 0);
};
Categories
Binary Tree Depth First Search Leetcode Recursion

Path Sum II

let pathSum = function(root, sum, results = [], result = []) {

    if (!root) return results;
    if (sum - root.val === 0 && !root.left && !root.right) {
        results.push([...result, root.val]);
    }

    pathSum(root.left, sum - root.val, results, [...result, root.val]);
    pathSum(root.right, sum - root.val, results, [...result, root.val]);
    return results;
};
Categories
Binary Tree Depth First Search Leetcode Recursion

Path Sum I

let hasPathSum = function(root, sum) {

    if (!root) return false;
    if (sum - root.val === 0 && !root.left && !root.right) return true;

    return hasPathSum(root.left, sum - root.val)
        || hasPathSum(root.right, sum - root.val);
};
Categories
Depth First Search Leetcode Recursion

Minesweeper

let updateBoard = function(board, click) {

    let maxRow = board.length,
        maxCol = board[0].length,
        MINE = 'M',
        BLANK = 'B',
        EMPTY = 'E',
        GAMEOVER = 'X';

    function isMine(row, col) {
        if (row < 0 || col < 0 || row >= maxRow || col >= maxCol) {
            return 0;
        }
        return board[row][col] === MINE ? 1 : 0;
    }

    function getMineCount(row, col) {
        let nearbyMines = 0;
        nearbyMines += isMine(row - 1, col - 1); // top left
        nearbyMines += isMine(row - 1, col); // top
        nearbyMines += isMine(row - 1, col + 1); // top right
        nearbyMines += isMine(row, col - 1); // left
        nearbyMines += isMine(row, col + 1); // right
        nearbyMines += isMine(row + 1, col - 1); // bottom left
        nearbyMines += isMine(row + 1, col); // bottom
        nearbyMines += isMine(row + 1, col + 1); // bottom right
        return nearbyMines;
    }

    function markAndExplore(row, col) {
        if (row < 0 || col < 0 || row >= maxRow || col >= maxCol) {
            return;
        }
        const data = board[row][col];
        if (data === EMPTY) {

            const mineCount = getMineCount(row, col);
            board[row][col] = mineCount > 0 ? `${mineCount}` : BLANK;

            if (mineCount === 0) {
                markAndExplore(row - 1, col - 1); // top left
                markAndExplore(row - 1, col); // top
                markAndExplore(row - 1, col + 1); // top right
                markAndExplore(row, col - 1); // left
                markAndExplore(row, col + 1); // right
                markAndExplore(row + 1, col - 1); // bottom left
                markAndExplore(row + 1, col); // bottom
                markAndExplore(row + 1, col + 1); // bottom right
            }
        }
    }

    let [x, y] = click;
    if (board[x][y] === MINE) {
        board[x][y] = GAMEOVER;
    }
    else {
        markAndExplore(x, y);
    }

    return board;
};
Categories
Depth First Search Leetcode Loop Recursion

Island Perimeter

let islandPerimeter = function(grid) {

    if (!grid || !grid.length) return 0;

    let maxRow = grid.length,
        maxCol = grid[0].length,
        LAND = 1, VISITED = 2;

    function calculatePerimeter(row, col) {

        if (grid[row][col] === LAND) {
            grid[row][col] = VISITED;

            let perimeter = 4;
            // check above;
            if (row > 0
                && (grid[row - 1][col] === LAND || grid[row - 1][col] === VISITED)) {
                perimeter = perimeter - 1;
                perimeter += calculatePerimeter(row - 1, col);
            }

            // check below;
            if (row < maxRow - 1
                && (grid[row + 1][col] === LAND || grid[row + 1][col] === VISITED)) {
                perimeter = perimeter - 1;
                perimeter += calculatePerimeter(row + 1, col);
            }

            // check left;
            if (col > 0
                && (grid[row][col - 1] === LAND || grid[row][col - 1] === VISITED)) {
                perimeter = perimeter - 1;
                perimeter += calculatePerimeter(row, col - 1);
            }

            // check right;
            if (col < maxCol - 1
                && (grid[row][col + 1] === LAND || grid[row][col + 1] === VISITED)) {
                perimeter = perimeter - 1;
                perimeter += calculatePerimeter(row, col + 1);
            }

            return perimeter; //?
        }

        return 0;
    }

    for (let row = 0; row < maxRow; row++) {
        for (let col = 0; col < maxCol;col++) {
            if (grid[row][col] === LAND) {
                return calculatePerimeter(row, col);
            }
        }
    }

    return 0;

};
Categories
Depth First Search Leetcode Recursion

Max Area of Island

let maxAreaOfIsland = function(grid) {

    if (!grid || !grid.length) return 0;

    let max = 0,
        maxRow = grid.length,
        maxCol = grid[0].length,
        LAND = 1, VISITED = 2;

    function markAndGetTotal(row, col) {
        if (row < 0 || row >= maxRow || col < 0 || col >= maxCol) return 0;
        if (grid[row][col] === LAND) {
            grid[row][col] = VISITED;

            let result = 1;
            // top
            result += markAndGetTotal(row - 1, col);
            // bottom
            result += markAndGetTotal(row + 1, col);
            // left
            result += markAndGetTotal(row, col - 1);
            /// right
            result += markAndGetTotal(row, col + 1);
            return result;
        }
        return 0;
    }

    for (let row = 0; row < maxRow;row++) {
        for (let col = 0; col < maxCol;col++) {
            if (grid[row][col] === LAND) {
                const total = markAndGetTotal(row, col); //?
                max = Math.max(total, max);
            }
        }
    }

    return max;
};