64 ms straight forward c++ DFS solution, beat 100%


  • 0
    Y

    First round of code submission.

    class Solution {
        int mMaxLen, mTracker;
        int m, n;
        void dfs(vector<vector<int>>& matrix, vector<vector<int>>& memo, int i, int j) {
            if (memo[i][j] != 0) {
                mTracker = max(mTracker, memo[i][j]);
                return;
            } else {
                mTracker = 0;
                if (i > 0 && matrix[i][j] < matrix[i-1][j]) {
                    dfs(matrix, memo, i-1, j);
                    memo[i][j] = max(memo[i][j], mTracker + 1);
                }
                if (i < m - 1 && matrix[i][j] < matrix[i+1][j]) {
                    dfs(matrix, memo, i+1, j);
                    memo[i][j] = max(memo[i][j], mTracker + 1);
                }
                if (j > 0 && matrix[i][j] < matrix[i][j-1]) {
                    dfs(matrix, memo, i, j-1);
                    memo[i][j] = max(memo[i][j], mTracker + 1);
                }
                if (j < n - 1 && matrix[i][j] < matrix[i][j+1]) {
                    dfs(matrix, memo, i, j+1);
                    memo[i][j] = max(memo[i][j], mTracker + 1);
                }
            }
            mTracker = max(++mTracker, memo[i][j]);
            memo[i][j] = max(memo[i][j], mTracker);
            mMaxLen = max(mTracker, mMaxLen);
        }
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            if (matrix.empty()) {
                return 0;
            }
            m = matrix.size();
            n = matrix[0].size();
            vector<vector<int>> memo(m, vector<int>(n, 0));
            mMaxLen = 0; mTracker = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                     if (memo[i][j] == 0) {
                        dfs(matrix, memo, i, j);
                    }
                }
            }
            /** uncomment to display memo walk route
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    cout << memo[i][j] << ' ';
                }
                cout << '\n';
            }
            */
            return mMaxLen;
        }
    };

Log in to reply
 

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