C++ O(mn) solution with dfs


  • 0
    J
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& history, int row, int col) {
        if(history[row][col] > 0) 
            return history[row][col];
        
        int l = 0, r = 0, u = 0, d = 0;
        
        if(row > 0) {
            if(matrix[row-1][col] > matrix[row][col]) 
                u = dfs(matrix, history, row - 1, col);
        }
        if(col > 0) {
            if(matrix[row][col-1] > matrix[row][col]) 
                l = dfs(matrix, history, row, col - 1);
        }
        if(row < matrix.size() - 1) {
            if(matrix[row+1][col] > matrix[row][col]) 
                d = dfs(matrix, history, row + 1, col);
        }
        if(col < matrix[0].size() - 1) {
            if(matrix[row][col+1] > matrix[row][col]) 
                r = dfs(matrix, history, row, col + 1);
        }
        
        history[row][col] = max(max(l, r), max(u, d)) + 1;
    }
    
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.size() == 0) return 0;
        
        vector<vector<int>> history (matrix.size(), vector<int>(matrix[0].size(), 0));
        
        int length = 0;
        for(int i = 0; i<matrix.size(); i++) {
            for(int j = 0; j<matrix[i].size(); j++) {
                length = max(length, dfs(matrix, history, i, j));
            }
        }
        
        return length;
    }

Log in to reply
 

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