30ms DP Java


  • 0
    A

    Would appreciate if someone could help me figure out what extra work I'm doing that's causing my solution to run ~30ms instead of 15ms.
    Comments explain the code. Basic idea is check to see if each element is the end of an increasing path by checking to see if its greater than its surrounding 4 values. Than I compute the length of the longest increasing path which ends with that value by getting the longest increasing paths that end with the 4 surrounding values and taking their max. After computing a longest increasing path I store it to ensure I don't repeat the computation.

    class Solution {
        
        private int[][] stor;
        private int[][] matrix;
        public int longestIncreasingPath(int[][] matrix) {
            if (matrix.length == 0) return 0;
            
            // Storing paths that we've already computed
            stor = new int[matrix.length][matrix[0].length];
            
            this.matrix = matrix;
            int max = 1; // max path len 
            
            // Iterate row by row from left to right over matrix
            for (int i = 0; i < matrix.length; i++) { 
                for (int j = 0; j < matrix[0].length; j++) {
                    int val = matrix[i][j];
                    // Check to see if value is the last value of a path by seeing if its greater 
                    // than all 4 surrounding values. 
                    if ((j == 0 || val >= matrix[i][j - 1]) && (j == matrix[0].length - 1 || val >= matrix[i][j + 1])
                    && (i == 0 || val >= matrix[i - 1][j]) && (i == matrix.length - 1 || val >= matrix[i + 1][j])) {
                        int pathLen = getPathLen(i, j);
                        max = Math.max(max, pathLen);
                    }
                }
            }
            return max;
        }
        
        // Takes the max of the 4 surrounding path lengths of a cell and adds 1 to it to get 
        // the path length of the given cell. 
        // Stores it for future use and returns the result. 
        private int getPathLen(int i, int j) {
            // If we haven't stored the path len we compute it. 
            if (stor[i][j] == 0) {
                // get max of paths which are less than cur
                int val = matrix[i][j];
                int maxOffset = 0;
                if (j > 0 && val > matrix[i][j - 1]) { // check left;
                    maxOffset = Math.max(maxOffset, getPathLen(i, j - 1));
                } 
                if (j < matrix[0].length - 1 && val > matrix[i][j + 1]) { // check right;
                    maxOffset = Math.max(maxOffset, getPathLen(i, j + 1));
                }
                if (i > 0 && val > matrix[i - 1][j]) { // check top;
                    maxOffset = Math.max(maxOffset, getPathLen(i - 1, j));
                }
                if (i < matrix.length - 1 && val > matrix[i + 1][j]) { // check bot;
                    maxOffset = Math.max(maxOffset, getPathLen(i + 1, j));
                }
                stor[i][j] = 1 + maxOffset;
                return stor[i][j];
            } else { // If we've stored the path len we just return it. 
                return stor[i][j];
            }
        }
    }
    

Log in to reply
 

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