JavaScript O(n*m) using memoization


  • 0
    F

    The brute approach with memoization to reduce complexity to O(nm) using also O(nm) space.

    var minPathSum = function(grid, memo={}, row=0, col=0) {
        if (!grid.length || !grid[0].length) { return 0; }
        if (hasmemo(memo, row, col)) { return getmemo(memo, row, col); }
        
        const height = grid.length;
        const width = grid[0].length;
        let val = grid[row][col];
        
        // Case bottom right corner (stop)
        if (row === height-1 && col === width-1) {
            return setmemo(memo,row,col,val);
        }
        // Case bottom row (we can only go right)
        if (row === height-1) {
            const min = val + minPathSum(grid, memo, row, col+1);
            return setmemo(memo,row,col,min);
        }
        // Case rightmost column (we can only go down)
        if (col === width-1) {
            const min = val + minPathSum(grid, memo, row+1, col);
            return setmemo(memo,row,col,min);
        }
        // Regular case, take the min of going to the right or going to the bottom
        const min = val + Math.min(minPathSum(grid, memo, row, col+1), minPathSum(grid, memo, row+1, col));
        return setmemo(memo,row,col,min);
    };
    
    /* memoization utilities */
    
    function setmemo(memo, row, col, val) {
        memo[row] = memo[row] || {};
        memo[row][col] = val;
        return val;
    }
    
    function getmemo(memo, row, col) {
        return memo[row][col];
    }
    
    function hasmemo(memo, row, col) {
        return (memo[row] && memo[row][col]) !== undefined;
    }
    

Log in to reply
 

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