LeetCode329: Longest Increasing Path in a Matrix

Here is a very nice solution from the LeetCode community.

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        
        // some boundary cases
        if (matrix.empty()) return 0;
        
        int nrow = matrix.size();
        int ncol = matrix[0].size();
        
        vector<vector<int>> hashtable(nrow, vector<int>(ncol, 0));
        
        int record = 1;
        
        for (int i = 0; i < nrow; ++i) {
            for (int j = 0; j < ncol; ++j) {
                record = max(record, helper(matrix, i,j, matrix[i][j] - 1, hashtable));
            }
        }
        
        return record;
    }
    
    int helper(vector<vector<int>>& matrix, int i, int j, int level, vector<vector<int>>& hashtable) {
        // see comments at the end of this section.

        if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size()) return 0;
        
        vector<int> di{1,-1,0,0};
        vector<int> dj{0,0,1,-1};
        

        // level keeps the information from previous step. Note that this function is trigger by an 
        // adjacent cell so if current value matrix[i][j] is less than to equal to level, we should return 0
        // it means that given the level, the contribution of current cell is zero.

        // this step is very important in the sense that it breaks the infinite recursive call.
        // Suppose we are at cell (i, j) and we will go through all the adjacent cells. Let say
        // we are now at cell (i, j+1). We will be allowed to go back to cell (i,j) again becasue 
        // it is one of the adjacent cells of the cell (i, j+1) 

        int curr_val = matrix[i][j];
        if (curr_val <= level) return 0;
        
        
        // hashtable memorizes previous calculation. If we have already met the cell (i,j) before, we should
        // have the result ready.
        if (hashtable[i][j] != 0) return hashtable[i][j];
        
        
        // If we arrive here, we need to do the computation to get the value for cell (i,j)
        int record = numeric_limits<int>::min();
        
        // iterate through the adjacent cells.
        // the "1" in the formula of record is important. It comes from the fact that the current
        // cell will contribute at least 1 to the final longest strict increasing subsequence.

        for (int k = 0; k < 4; ++k) {
            record = max(record, 1 + helper(matrix, i + di[k], j + dj[k], curr_val, hashtable));
        }

        // we now have a clearer view of the hashtable. hashtable[i][j] records the longest length of the strictly 
        // increasing subsequence which starts from hashtable[i][j]
        
        hashtable[i][j] = max(hashtable[i][j], record);
        
        return record;
        
        
        
    }
};