Java Solution: O(mn) Backtracking/DFS + DP: Accepted


  • 2
    V

    I am simply using Backtracking while storing the calculated values. I have added comments in the code. In case of any problem please add a comment.
    The code can be written in fewer lines however that will reduce the readability and slows the debugging process.

    public class Solution {
    
        // There can be no repetetion of elements as the sequence must be strictly increasing.
        // So we don't have to worry about loops. It will be handled implicitly.
    
        int[][] solution;
        int maxLength;
        public int longestIncreasingPath(int[][] matrix) {
            if(matrix==null || matrix.length==0){
                return 0;
            }
            solution=new int[matrix.length][matrix[0].length];
            maxLength=1; // default value
    
            // Calculating the value for each cell.
    		int j;
            for (int i = 0; i < matrix.length; i++) {
                for (j = 0; j < matrix[0].length; j++) {
                        increasingSequence(matrix,i,j);
                }
            }
            return maxLength;
        }
    
        public int increasingSequence(int[][] matrix, int i, int j){
    
            // checking if already calculated, in case of already calculted value solution[i][j] will be > 0
            if(solution[i][j]>0) {
                return solution[i][j];
            }
            solution[i][j]=1;
            // for the four sides we can go to
            int one, two, three, four;
            one=two=three=four=0;
            if(matrix[max(i-1,0)][j]>matrix[i][j]) {
                one = increasingSequence(matrix, max(i - 1, 0), j);
            }
            if(matrix[min(i + 1, matrix.length - 1)][j]>matrix[i][j]) {
                two = increasingSequence(matrix, min(i + 1, matrix.length - 1), j);
            }
            if(matrix[i][max(j-1,0)]>matrix[i][j]) {
                three = increasingSequence(matrix, i, max(j - 1, 0));
            }
            if(matrix[i][min(j+1,matrix[0].length-1)]>matrix[i][j]) {
                four = increasingSequence(matrix, i, min(j + 1, matrix[0].length - 1));
            }
            // getting the max value among the four. Updating maxLength accordingly.
            solution[i][j]=max(one,two,three,four)+1;
            if(solution[i][j]>maxLength){
                maxLength=solution[i][j];
            }
            return solution[i][j];
        }
    
        // basic util functions
        public int max(int a, int b){
            return a>=b?a:b;
        }
    
        public int max(int a, int b, int c, int d){
            int temp1=c>=d?c:d;
            return a>=b?a>=temp1?a:temp1:b>=temp1?b:temp1;
        }
    
        public int min(int a, int b){
            return a<=b?a:b;
        }
    }
    

    In case of any improvements, no matter how small, please add a comment.
    Thanks in advance.


Log in to reply
 

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