JavaScript, DFS in O(m*n)


  • 0
    F
    var longestIncreasingPath = function(matrix) {
        /* Edge cases, empty matrix */
        const h = matrix.length;
        if (!h) { return 0;}
        const w = matrix[0].length;
        if (!w) { return 0; }
        
        /* lengths[i][j] will store the longest increasing path starting at [i, j] */
        const lengths = new Array(h);
        for (let i=0; i<h; i++) {
            lengths[i] = new Array(w);
        }
        
        /* Traverse the matrix and generate local increasing path for each cell */
        let max = 0;
        for (let row=0; row<h; row++) {
          for (let col=0; col<w; col++) {
            generateScore(lengths, row, col);
            max = Math.max(max, lengths[row][col]);
          }
        }
        return max;
    
        function generateScore(lengths, row, col) {
            if (lengths[row][col] !== undefined) { return lengths[row][col]; }
            let score = 1;
            const cell = matrix[row][col];
            if (row >  0 ) { check(row-1, col); }
            if (row < h-1) { check(row+1, col); }
            if (col >  0 ) { check(row, col-1); }
            if (col < w-1) { check(row, col+1); }
            lengths[row][col] = score;
            return score;
    
            function check(row, col) {
                if (matrix[row][col] > cell) {
                    score = Math.max(generateScore(lengths, row, col) + 1, score);
                }
            }
        }
    };
    

Log in to reply
 

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