C++ with good coding style ! Once AC after being interviewd .....


  • 2
    2
    class Solution {
        vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            int result=1;
            int m = matrix.size();
            if(m == 0)  return 0;
            int n = matrix[0].size();
            vector<vector<int>> visit(m, vector<int>(n, 1));
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    int temp = help(matrix, visit, i, j, m, n);
                    result = max(result, temp);
                }
            }
            return result;
        }
        
        int help(vector<vector<int>>& matrix, vector<vector<int>>& visit, int i, int j, int m, int n){
            if(visit[i][j]>1)  return visit[i][j];
            int result = 1;
            for(auto dir : dirs){
                int x = i + dir[0], y = j + dir[1];
                if(x < 0 || x >= m || y < 0 || y >= n || matrix[i][j] >= matrix[x][y])  continue;
                result = max(result, help(matrix, visit, x, y, m, n) + 1);
            }
            visit[i][j] = result;
            return result;
        }
    };

  • 0
    2

    The key is just that where to check the corner cases !


Log in to reply
 

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