64ms C++ solution, DFS + DP


  • 0
    A

    Basic DFS may result in TLE (Time Limit Exceeded) because of duplicate calculation. Thus it seems reasonable to sacrifice space for time: use a map for positions where max increasing length (starting from this position) has been calculated.
    See code below:

    class Solution {
    public:
        int maxLength = INT_MIN;
        vector<vector<int>> maxLengthMap;
        int DFS_VISIT(vector<vector<int>>& matrix, int i, int j, int maxRowNum, int maxColumnNum) {
            if (maxLengthMap[i][j] > 0) // If position (i,j) has already been calculated, no need for redundant work
                return maxLengthMap[i][j];
            int leftMaxLength = 0;
            int rightMaxLength = 0;
            int upMaxLength = 0;
            int downMaxLength = 0;
            if (j-1 <= maxColumnNum && j-1 >= 0 && matrix[i][j-1] > matrix[i][j]) { // Go left
                leftMaxLength = DFS_VISIT(matrix, i, j-1, maxRowNum, maxColumnNum);
            }
            if (j+1 <= maxColumnNum && j+1 >= 0 && matrix[i][j+1] > matrix[i][j]) { // Go right
                rightMaxLength = DFS_VISIT(matrix, i, j+1, maxRowNum, maxColumnNum);
            }   
            if (i-1 <= maxRowNum && i-1 >= 0 && matrix[i-1][j] > matrix[i][j]) { // Go up
                upMaxLength = DFS_VISIT(matrix, i-1, j, maxRowNum, maxColumnNum);
            }   
            if (i+1 <= maxRowNum && i+1 >= 0 && matrix[i+1][j] > matrix[i][j]) { // Go down
                downMaxLength = DFS_VISIT(matrix, i+1, j, maxRowNum, maxColumnNum);
            }
            // maxLength = max(maxLength,curLength);
            maxLengthMap[i][j] = max(max(leftMaxLength, rightMaxLength), max(upMaxLength, downMaxLength)) + 1;
            return maxLengthMap[i][j];
        }
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            int n = matrix.size(); // #rows
            if (n == 0)
                return 0;
            int m = matrix[0].size(); // #columns
            if (m == 0) // Empty input
                return 0;
    	vector<int> tempL(m,0);
    	for (int i=0;i<n;i++)
    	    maxLengthMap.push_back(tempL);
            for (int i=0;i<n;i++) {
                for (int j=0;j<m;j++) {
                    int curLength = DFS_VISIT(matrix, i, j, n-1, m-1); // DFS current position (i,j)
                    maxLength = max(maxLength, curLength);
                }
            }
            return maxLength;
        }
    };
    

Log in to reply
 

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