Beats 100% | 4 Solutions
\n# First Solution: Recursive DFS with Memoization (Top-Down)\n- Approach:\n1. Use a recursive DFS function getMoves with memoization to avoid redundant calcula
![image.png](https://assets.leetcode.com/users/images/3bfe9de7-cedf-4fb2-befe-cb71f5e536fe_1730182734.6880832.png)\n# First Solution: Recursive DFS with Memoization (Top-Down)\n- Approach:\n1. Use a recursive DFS function getMoves with memoization to avoid redundant calculations.\n2. For each cell in the first column, start a DFS to explore possible paths to the last column.\n3. Recursively find the maximum number of moves for each cell, checking the three adjacent cells in the next column.\n4. Memoize each cell\u2019s result in the dp table to avoid recalculating it on subsequent calls.\n- Complexity:\n    - Time Complexity: O(m\xD7n) due to memoized DFS across each cell.\n    - Space Complexity: O(m\xD7n) for the dp array and the recursion stack.\n# Code\n```cpp []\nclass Solution {\nprivate:\n    vector<vector<int>> dp;\n    vector<int> X = {-1,0,1};\n    vector<int> Y = {1,1,1};\n    bool isBoundary(int i,int j,int n,int m){\n        return (i>=0 && j>=0 && i<n && j<m);\n    }\n    int getMoves(int i,int j,vector<vector<int>> & grid){\n        if(dp[i][j] != -1) return dp[i][j];\n        int moves = 0;\n        for(int k=0; k<3; k++){\n            int x = i+X[k];\n            int y = j+Y[k];\n            if(isBoundary(x,y,grid.size(),grid[0].size()) && grid[x][y] > grid[i][j]){\n                moves = max(moves,1+getMoves(x,y,grid));\n            }\n        }\n        return dp[i][j] = moves;\n    }\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n\n        int res = 0;\n        dp.assign(grid.size(),vector<int>(grid[0].size(),-1));\n        for(int i=0; i<grid.size(); i++){\n            res = max(res,getMoves(i,0,grid));\n        }\n        return res;\n    }\n};\n```\n# Second Solution: Bottom-Up DP with 2D Array\n- Approach:\n1. Start filling the dp table from the last column to the first, calculating the maximum number of moves for each cell.\n2. For each cell, look at the three possible cells in the next column, adding one move if a greater value is found.\n3. Store the maximum moves for each cell in the dp table as we iterate from the last column to the first.\n4. Finally, check the values in the first column of dp to find the maximum moves starting from any cell.\n- Complexity:\n    - Time Complexity: O(m\xD7n), as each cell is processed once.\n    - Space Complexity: O(m\xD7n) due to the dp array.\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    vector<vector<int>> dp;\n    vector<int> X = {-1,0,1};\n    vector<int> Y = {1,1,1};\n    bool isBoundary(int i,int j,int n,int m){\n        return (i>=0 && j>=0 && i<n && j<m);\n    }\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int rows = grid.size();\n        int cols = grid[0].size();\n        vector<vector<int>> dp(rows, vector<int>(cols, 0)); // DP table to store max moves from each cell\n\n        // Traverse each column from the second-last to the first\n        for (int j = cols - 2; j >= 0; --j) {\n            for (int i = 0; i < rows; ++i) {\n                int maxMoves = 0;\n                // Check all three possible moves to the next column\n                for (int d = -1; d <= 1; ++d) { \n                    int ni = i + d;  // new row index\n                    int nj = j + 1;  // new column index\n\n                    if (ni >= 0 && ni < rows && grid[ni][nj] > grid[i][j]) {\n                        maxMoves = max(maxMoves, 1 + dp[ni][nj]);\n                    }\n                }\n                dp[i][j] = maxMoves;\n            }\n        }\n\n        // Find the max value in the first column of dp as the result\n        int result = 0;\n        for (int i = 0; i < rows; ++i) {\n            result = max(result, dp[i][0]);\n        }\n        return result;\n    }\n};\n```\n# Third Solution: Optimized Bottom-Up DP with Two 1D Arrays\n- Approach:\n1. Similar to the previous DP solution but optimized for space.\n2. Instead of using a 2D dp array, use two 1D arrays (dp and next_dp) representing the current column and the next column, respectively.\n3. For each column, update the moves in the dp array based on the values in next_dp.\n4. This reduces space usage significantly by only tracking the last two columns instead of all columns.\n- Complexity:\n    -Time Complexity: O(m\xD7n), as each cell is processed once.\n    - Space Complexity: O(m) using two 1D arrays.\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n\n        int rows = grid.size();\n        int cols = grid[0].size();\n\n        vector<int> dp(rows, 0);         // dp for current column\n        vector<int> next_dp(rows, 0);    // next_dp for the next column\n\n        // Traverse each column from the second-last to the first\n        for (int j = cols - 2; j >= 0; --j) {\n            for (int i = 0; i < rows; ++i) {\n                int maxMoves = 0;\n                // Check all three possible moves to the next column\n                for (int d = -1; d <= 1; ++d) {\n                    int ni = i + d; // new row index\n\n                    if (ni >= 0 && ni < rows && grid[ni][j + 1] > grid[i][j]) {\n                        maxMoves = max(maxMoves, 1 + next_dp[ni]);\n                    }\n                }\n                dp[i] = maxMoves;  // store result for this cell in current column\n            }\n            next_dp = dp;  // Move to the next column\n        }\n\n        // Find the max value in the first column of dp as the result\n        return *max_element(dp.begin(), dp.end());\n    }\n};\n```\n# Fourth Solution: Depth-First Search (DFS)\n- Intuition:\nThis solution utilizes a DFS approach to find the maximum path length from any cell in the first column to the last column. By exploring paths recursively and marking cells as visited by setting them to zero, the algorithm effectively traverses the grid while ensuring that cells are not revisited in the same path.\n\n- Approach:\n    1. Define a recursive dfs function that tracks the row (i) and column (j) of the current cell.\n    2. Update the result res with the maximum value of j (indicating how far in columns the path has reached).\n    3. Recursively call dfs on the next column (j+1) for the three possible row movements (i-1, i, i+1) if:\n        - The next cell is within bounds.\n        - The value in the next cell is greater than the current cell.\n    - After each call, mark the current cell as visited by setting it to 0 to avoid revisiting.\n4. Start DFS from each cell in the first column, updating res with the maximum depth reached in each traversal.\n- Complexity:\n    - Time Complexity: O(3*n\xD7m) in the worst case, due to the exhaustive search approach.\n    - Space Complexity: O(m\xD7n) due to the recursion stack depth and marking cells.\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n\n        int res = 0;\n        int rows = grid.size();\n        int cols = grid[0].size();\n\n        function<void(int,int)> dfs = [&] (int i,int j){\n            res = max(res,j);\n            if(res == cols-1) return;\n\n            for(int ii=max(0,i-1); ii<min(i+2,rows); ii++){\n                if(grid[ii][j+1] > grid[i][j])\n                    dfs(ii,j+1);\n            }\n            grid[i][j] = 0;\n        };\n\n        for(int i=0; i<rows; i++){\n            dfs(i,0);\n        }\n        return res;\n    }\n};\n```\n```Java []\nclass Solution {\n    int res = 0;\n    int rows, cols;\n    \n    public int maxMoves(int[][] grid) {\n        rows = grid.length;\n        cols = grid[0].length;\n\n        for (int i = 0; i < rows; i++) {\n            dfs(i, 0, grid);\n        }\n        return res;\n    }\n    \n    private void dfs(int i, int j, int[][] grid) {\n        res = Math.max(res, j);\n        if (res == cols - 1) return;\n\n        for (int d = -1; d <= 1; d++) {\n            int ni = i + d;\n            if (ni >= 0 && ni < rows && grid[ni][j + 1] > grid[i][j]) {\n                dfs(ni, j + 1, grid);\n            }\n        }\n        grid[i][j] = 0;  // Mark as visited\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        res = 0\n        rows, cols = len(grid), len(grid[0])\n\n        def dfs(i, j):\n            nonlocal res\n            res = max(res, j)\n            if res == cols - 1:\n                return\n            for d in (-1, 0, 1):\n                ni = i + d\n                if 0 <= ni < rows and grid[ni][j + 1] > grid[i][j]:\n                    dfs(ni, j + 1)\n            grid[i][j] = 0  # Mark as visited\n\n        for i in range(rows):\n            dfs(i, 0)\n        return res\n\n```\n```Javascript []\nvar maxMoves = function(grid) {\n    let res = 0;\n    const rows = grid.length, cols = grid[0].length;\n\n    const dfs = (i, j) => {\n        res = Math.max(res, j);\n        if (res === cols - 1) return;\n\n        for (let d = -1; d <= 1; d++) {\n            const ni = i + d;\n            if (ni >= 0 && ni < rows && grid[ni][j + 1] > grid[i][j]) {\n                dfs(ni, j + 1);\n            }\n        }\n        grid[i][j] = 0;  // Mark as visited\n    };\n\n    for (let i = 0; i < rows; i++) {\n        dfs(i, 0);\n    }\n    return res;\n};\n\n```\n![Please hit the upvote button (1).png](https://assets.leetcode.com/users/images/194e7fc5-9a68-4222-a9c3-d2c96128bf7a_1730183015.4224045.png)\n
['Array', 'Dynamic Programming', 'Depth-First Search', 'Memoization', 'Matrix', 'C++', 'Java', 'Python3', 'JavaScript']