JavaScript - Easy to follow solution


  • 0
    O

    This solution is a little slower than some of the more efficient solutions, but is highly commented and cleanly written so as to be easy to understand. Passes every test.

    // Build the elements into nodes for easier traversal.
    var buildElements = function (matrix) {
        var elements = [],
            elementsMap = {}, // We're putting elements into this map using index keys to make finding them faster.
            element,
            leftKey,
            topKey,
            i, j;
        
        for (i = 0; i < matrix.length; i++) {
            for (j = 0; j < matrix[i].length; j++) {
                // Get the keys for top and left element. Don't need to check bottom and right because they will be
                // mapped automatically as we go through.
                leftKey = i + ":" + (j-1);
                topKey = (i-1) + ":" + j;
                element = {
                    val: matrix[i][j],
                    adjacent: []
                };
                
                // If check should only be false on first row
                if (elementsMap[topKey]) {
                    // Map the found element as this ones top and this element as the found elements bottom.
                    element.adjacent.push(elementsMap[topKey]);
                    elementsMap[topKey].adjacent.push(element);
                }
                
                // If check should only be false on first column
                if (elementsMap[leftKey]) {
                    // Map the found element as this ones left and this element as the found ones right.
                    element.adjacent.push(elementsMap[leftKey]);
                    elementsMap[leftKey].adjacent.push(element);
                }
                
                elementsMap[i + ":" + j] = element; // Add this element to the map
                elements.push(element); // Also put it in the list (which we will use later for traversal)
            }
        }
        
        return elements;
    };
    
    var findLongestPath = function (element) {
        var longestPath = 0,
            currPath,
            index,
            adjacentElement;
            
        // If we've already traversed this element, just return what we found
        if (element.longestPath) {
            return element.longestPath;
        }
        
        for (index = 0; index < element.adjacent.length; index++) {
            adjacentElement = element.adjacent[index];
            
            // If the current adjacent element has a larger value, find its longest path
            if (adjacentElement.val > element.val) {
                currPath = findLongestPath(adjacentElement);
            } else {
                currPath = 0;
            }
            
            // If the found longest path is greater than the current best, replace it
            if (currPath > longestPath) {
                longestPath = currPath;
            }
        }
        
        // Increment by one to account for the element you are looking at.
        longestPath++;
        
        // Assign the longest path to the element so you don't have to traverse it again.
        element.longestPath = longestPath;
        return longestPath;
    };
    
    /**
     * @param {number[][]} matrix
     * @return {number}
     */
    var longestIncreasingPath = function(matrix) {
        var elements = buildElements(matrix), // Build the element object list
            index,
            longestPath = 0,
            currPath;
        
        // Traverse the list to find the element which returns the longest path.
        for (index = 0; index < elements.length; index++) {
            currPath = findLongestPath(elements[index]);
            if (currPath > longestPath) {
                longestPath = currPath;
            }
        }
        
        return longestPath;
    };

Log in to reply
 

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