✅ List Most Common Interview Matrix | Beats 100% | ✅ Explained step by step
python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        # Get dimensions of the grid\n        m = len(grid)    # number of r
```python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        # Get dimensions of the grid\n        m = len(grid)    # number of rows\n        n = len(grid[0]) # number of columns\n        \n        # res will store the rightmost column we can reach\n        res = 0\n        \n        # dp array stores the maximum number of moves possible to reach each cell\n        # in the current column we\'re processing\n        dp = [0] * m\n        \n        # Iterate through each column from left to right (starting from column 1)\n        for j in range(1, n):\n            # leftTop keeps track of the dp value from the cell above-left\n            leftTop = 0\n            # found indicates if we can reach any cell in current column\n            found = False\n            \n            # Iterate through each row in current column\n            for i in range(m):\n                # cur will store the maximum moves to reach current cell\n                cur = -1\n                # Store dp[i] for next iteration\'s leftTop\n                nxtLeftTop = dp[i]\n                \n                # Check move from top-left cell (if valid)\n                if i - 1 >= 0 and leftTop != -1 and grid[i][j] > grid[i-1][j-1]:\n                    cur = max(cur, leftTop + 1)\n                \n                # Check move from direct left cell (if valid)\n                if dp[i] != -1 and grid[i][j] > grid[i][j-1]:\n                    cur = max(cur, dp[i] + 1)\n                \n                # Check move from bottom-left cell (if valid)\n                if i + 1 < m and dp[i+1] != -1 and grid[i][j] > grid[i+1][j-1]:\n                    cur = max(cur, dp[i+1] + 1)\n                \n                # Update dp array for current cell\n                dp[i] = cur\n                # Update found flag if we can reach current cell\n                found = found or (dp[i] != -1)\n                # Update leftTop for next row\'s iteration\n                leftTop = nxtLeftTop\n            \n            # If we can\'t reach any cell in current column, break\n            if not found:\n                break\n            # Update result to current column if we can reach it\n            res = j\n        \n        # Return the maximum number of moves possible\n        return res\n```\n```cpp []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        // Get dimensions of the grid\n        int m = grid.size();    // number of rows\n        int n = grid[0].size(); // number of columns\n        \n        // res will store the rightmost column we can reach\n        int res = 0;\n        \n        // dp array stores the maximum number of moves possible to reach each cell\n        // in the current column we\'re processing\n        vector<int> dp(m);\n        \n        // Iterate through each column from left to right (starting from column 1)\n        for (int j = 1; j < n; ++j) {\n            // leftTop keeps track of the dp value from the cell above-left\n            int leftTop = 0;\n            // found indicates if we can reach any cell in current column\n            bool found = false;\n            \n            // Iterate through each row in current column\n            for (int i = 0; i < m; ++i) {\n                // cur will store the maximum moves to reach current cell\n                int cur = -1;\n                // Store dp[i] for next iteration\'s leftTop\n                int nxtLeftTop = dp[i];\n                \n                // Check move from top-left cell (if valid)\n                if (i - 1 >= 0 && leftTop != -1 && grid[i][j] > grid[i - 1][j - 1]) {\n                    cur = max(cur, leftTop + 1);\n                }\n                \n                // Check move from direct left cell (if valid)\n                if (dp[i] != -1 && grid[i][j] > grid[i][j - 1]) {\n                    cur = max(cur, dp[i] + 1);\n                }\n                \n                // Check move from bottom-left cell (if valid)\n                if (i + 1 < m && dp[i + 1] != -1 && grid[i][j] > grid[i + 1][j - 1]) {\n                    cur = max(cur, dp[i + 1] + 1);\n                }\n                \n                // Update dp array for current cell\n                dp[i] = cur;\n                // Update found flag if we can reach current cell\n                found = found || (dp[i] != -1);\n                // Update leftTop for next row\'s iteration\n                leftTop = nxtLeftTop;\n            }\n            \n            // If we can\'t reach any cell in current column, break\n            if (!found) break;\n            // Update result to current column if we can reach it\n            res = j;\n        }\n        \n        // Return the maximum number of moves possible\n        return res;\n    }\n};\n```\n```java []\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        // Get dimensions of the grid\n        int m = grid.length;    // number of rows\n        int n = grid[0].length; // number of columns\n        \n        // res will store the rightmost column we can reach\n        int res = 0;\n        \n        // dp array stores the maximum number of moves possible to reach each cell\n        // in the current column we\'re processing\n        int[] dp = new int[m];\n        \n        // Iterate through each column from left to right (starting from column 1)\n        for (int j = 1; j < n; j++) {\n            // leftTop keeps track of the dp value from the cell above-left\n            int leftTop = 0;\n            // found indicates if we can reach any cell in current column\n            boolean found = false;\n            \n            // Iterate through each row in current column\n            for (int i = 0; i < m; i++) {\n                // cur will store the maximum moves to reach current cell\n                int cur = -1;\n                // Store dp[i] for next iteration\'s leftTop\n                int nxtLeftTop = dp[i];\n                \n                // Check move from top-left cell (if valid)\n                if (i - 1 >= 0 && leftTop != -1 && grid[i][j] > grid[i - 1][j - 1]) {\n                    cur = Math.max(cur, leftTop + 1);\n                }\n                \n                // Check move from direct left cell (if valid)\n                if (dp[i] != -1 && grid[i][j] > grid[i][j - 1]) {\n                    cur = Math.max(cur, dp[i] + 1);\n                }\n                \n                // Check move from bottom-left cell (if valid)\n                if (i + 1 < m && dp[i + 1] != -1 && grid[i][j] > grid[i + 1][j - 1]) {\n                    cur = Math.max(cur, dp[i + 1] + 1);\n                }\n                \n                // Update dp array for current cell\n                dp[i] = cur;\n                // Update found flag if we can reach current cell\n                found = found || (dp[i] != -1);\n                // Update leftTop for next row\'s iteration\n                leftTop = nxtLeftTop;\n            }\n            \n            // If we can\'t reach any cell in current column, break\n            if (!found) break;\n            // Update result to current column if we can reach it\n            res = j;\n        }\n        \n        // Return the maximum number of moves possible\n        return res;\n    }\n}\n```\n```csharp []\npublic class Solution {\n    public int MaxMoves(int[][] grid) {\n        // Get dimensions of the grid\n        int m = grid.Length;     // number of rows\n        int n = grid[0].Length;  // number of columns\n        \n        // res will store the rightmost column we can reach\n        int res = 0;\n        \n        // dp array stores the maximum number of moves possible to reach each cell\n        // in the current column we\'re processing\n        int[] dp = new int[m];\n        \n        // Iterate through each column from left to right (starting from column 1)\n        for (int j = 1; j < n; j++) {\n            // leftTop keeps track of the dp value from the cell above-left\n            int leftTop = 0;\n            // found indicates if we can reach any cell in current column\n            bool found = false;\n            \n            // Iterate through each row in current column\n            for (int i = 0; i < m; i++) {\n                // cur will store the maximum moves to reach current cell\n                int cur = -1;\n                // Store dp[i] for next iteration\'s leftTop\n                int nxtLeftTop = dp[i];\n                \n                // Check move from top-left cell (if valid)\n                if (i - 1 >= 0 && leftTop != -1 && grid[i][j] > grid[i - 1][j - 1]) {\n                    cur = Math.Max(cur, leftTop + 1);\n                }\n                \n                // Check move from direct left cell (if valid)\n                if (dp[i] != -1 && grid[i][j] > grid[i][j - 1]) {\n                    cur = Math.Max(cur, dp[i] + 1);\n                }\n                \n                // Check move from bottom-left cell (if valid)\n                if (i + 1 < m && dp[i + 1] != -1 && grid[i][j] > grid[i + 1][j - 1]) {\n                    cur = Math.Max(cur, dp[i + 1] + 1);\n                }\n                \n                // Update dp array for current cell\n                dp[i] = cur;\n                // Update found flag if we can reach current cell\n                found = found || (dp[i] != -1);\n                // Update leftTop for next row\'s iteration\n                leftTop = nxtLeftTop;\n            }\n            \n            // If we can\'t reach any cell in current column, break\n            if (!found) break;\n            // Update result to current column if we can reach it\n            res = j;\n        }\n        \n        // Return the maximum number of moves possible\n        return res;\n    }\n}\n```\n```golang []\nfunc maxMoves(grid [][]int) int {\n    m := len(grid)    // number of rows\n    n := len(grid[0]) // number of columns\n    \n    // res will store the rightmost column we can reach\n    res := 0\n    \n    // dp array stores the maximum number of moves possible to reach each cell\n    // in the current column we\'re processing\n    dp := make([]int, m)\n    \n    // Iterate through each column from left to right (starting from column 1)\n    for j := 1; j < n; j++ {\n        // leftTop keeps track of the dp value from the cell above-left\n        leftTop := 0\n        // found indicates if we can reach any cell in current column\n        found := false\n        \n        // Iterate through each row in current column\n        for i := 0; i < m; i++ {\n            // cur will store the maximum moves to reach current cell\n            cur := -1\n            // Store dp[i] for next iteration\'s leftTop\n            nxtLeftTop := dp[i]\n            \n            // Check move from top-left cell (if valid)\n            if i-1 >= 0 && leftTop != -1 && grid[i][j] > grid[i-1][j-1] {\n                cur = max(cur, leftTop+1)\n            }\n            \n            // Check move from direct left cell (if valid)\n            if dp[i] != -1 && grid[i][j] > grid[i][j-1] {\n                cur = max(cur, dp[i]+1)\n            }\n            \n            // Check move from bottom-left cell (if valid)\n            if i+1 < m && dp[i+1] != -1 && grid[i][j] > grid[i+1][j-1] {\n                cur = max(cur, dp[i+1]+1)\n            }\n            \n            // Update dp array for current cell\n            dp[i] = cur\n            // Update found flag if we can reach current cell\n            found = found || (dp[i] != -1)\n            // Update leftTop for next row\'s iteration\n            leftTop = nxtLeftTop\n        }\n        \n        // If we can\'t reach any cell in current column, break\n        if !found {\n            break\n        }\n        // Update result to current column if we can reach it\n        res = j\n    }\n    \n    // Return the maximum number of moves possible\n    return res\n}\n\n// Helper function to find maximum of two integers\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n```\n```swift []\nclass Solution {\n    func maxMoves(_ grid: [[Int]]) -> Int {\n        // Get dimensions of the grid\n        let m = grid.count      // number of rows\n        let n = grid[0].count   // number of columns\n        \n        // res will store the rightmost column we can reach\n        var res = 0\n        \n        // dp array stores the maximum number of moves possible to reach each cell\n        // in the current column we\'re processing\n        var dp = Array(repeating: 0, count: m)\n        \n        // Iterate through each column from left to right (starting from column 1)\n        for j in 1..<n {\n            // leftTop keeps track of the dp value from the cell above-left\n            var leftTop = 0\n            // found indicates if we can reach any cell in current column\n            var found = false\n            \n            // Iterate through each row in current column\n            for i in 0..<m {\n                // cur will store the maximum moves to reach current cell\n                var cur = -1\n                // Store dp[i] for next iteration\'s leftTop\n                let nxtLeftTop = dp[i]\n                \n                // Check move from top-left cell (if valid)\n                if i - 1 >= 0 && leftTop != -1 && grid[i][j] > grid[i-1][j-1] {\n                    cur = max(cur, leftTop + 1)\n                }\n                \n                // Check move from direct left cell (if valid)\n                if dp[i] != -1 && grid[i][j] > grid[i][j-1] {\n                    cur = max(cur, dp[i] + 1)\n                }\n                \n                // Check move from bottom-left cell (if valid)\n                if i + 1 < m && dp[i+1] != -1 && grid[i][j] > grid[i+1][j-1] {\n                    cur = max(cur, dp[i+1] + 1)\n                }\n                \n                // Update dp array for current cell\n                dp[i] = cur\n                // Update found flag if we can reach current cell\n                found = found || (dp[i] != -1)\n                // Update leftTop for next row\'s iteration\n                leftTop = nxtLeftTop\n            }\n            \n            // If we can\'t reach any cell in current column, break\n            if !found { break }\n            // Update result to current column if we can reach it\n            res = j\n        }\n        \n        // Return the maximum number of moves possible\n        return res\n    }\n}\n```\n```javascript [JS]\n// JavaScript\n\n/**\n * @param {number[][]} grid\n * @return {number}\n */\nvar maxMoves = function(grid) {\n    // Get dimensions of the grid\n    const m = grid.length;    // number of rows\n    const n = grid[0].length; // number of columns\n    \n    // res will store the rightmost column we can reach\n    let res = 0;\n    \n    // dp array stores the maximum number of moves possible to reach each cell\n    // in the current column we\'re processing\n    let dp = new Array(m).fill(0);\n    \n    // Iterate through each column from left to right (starting from column 1)\n    for (let j = 1; j < n; j++) {\n        // leftTop keeps track of the dp value from the cell above-left\n        let leftTop = 0;\n        // found indicates if we can reach any cell in current column\n        let found = false;\n        \n        // Iterate through each row in current column\n        for (let i = 0; i < m; i++) {\n            // cur will store the maximum moves to reach current cell\n            let cur = -1;\n            // Store dp[i] for next iteration\'s leftTop\n            let nxtLeftTop = dp[i];\n            \n            // Check move from top-left cell (if valid)\n            if (i - 1 >= 0 && leftTop !== -1 && grid[i][j] > grid[i - 1][j - 1]) {\n                cur = Math.max(cur, leftTop + 1);\n            }\n            \n            // Check move from direct left cell (if valid)\n            if (dp[i] !== -1 && grid[i][j] > grid[i][j - 1]) {\n                cur = Math.max(cur, dp[i] + 1);\n            }\n            \n            // Check move from bottom-left cell (if valid)\n            if (i + 1 < m && dp[i + 1] !== -1 && grid[i][j] > grid[i + 1][j - 1]) {\n                cur = Math.max(cur, dp[i + 1] + 1);\n            }\n            \n            // Update dp array for current cell\n            dp[i] = cur;\n            // Update found flag if we can reach current cell\n            found = found || (dp[i] !== -1);\n            // Update leftTop for next row\'s iteration\n            leftTop = nxtLeftTop;\n        }\n        \n        // If we can\'t reach any cell in current column, break\n        if (!found) break;\n        // Update result to current column if we can reach it\n        res = j;\n    }\n    \n    // Return the maximum number of moves possible\n    return res;\n};\n```\n```typescript [TS]\nfunction maxMoves(grid: number[][]): number {\n    const m: number = grid.length;    \n    const n: number = grid[0].length; \n    \n    let res: number = 0;\n    let dp: number[] = new Array(m).fill(0);\n    \n    for (let j = 1; j < n; j++) {\n        let leftTop: number = 0;\n        let found: boolean = false;\n        \n        for (let i = 0; i < m; i++) {\n            let cur: number = -1;\n            let nxtLeftTop: number = dp[i];\n            \n            if (i - 1 >= 0 && leftTop !== -1 && grid[i][j] > grid[i - 1][j - 1]) {\n                cur = Math.max(cur, leftTop + 1);\n            }\n            \n            if (dp[i] !== -1 && grid[i][j] > grid[i][j - 1]) {\n                cur = Math.max(cur, dp[i] + 1);\n            }\n            \n            if (i + 1 < m && dp[i + 1] !== -1 && grid[i][j] > grid[i + 1][j - 1]) {\n                cur = Math.max(cur, dp[i + 1] + 1);\n            }\n            \n            dp[i] = cur;\n            found = found || (dp[i] !== -1);\n            leftTop = nxtLeftTop;\n        }\n        \n        if (!found) break;\n        res = j;\n    }\n    \n    return res;\n}\n```\n```rust []\nimpl Solution {\n    pub fn max_moves(grid: Vec<Vec<i32>>) -> i32 {\n        let m = grid.len();    // number of rows\n        let n = grid[0].len(); // number of columns\n        \n        let mut res = 0;\n        let mut dp = vec![0; m];\n        \n        for j in 1..n {\n            let mut left_top = 0;\n            let mut found = false;\n            \n            for i in 0..m {\n                let mut cur = -1;\n                let next_left_top = dp[i];\n                \n                // Check move from top-left cell\n                if i > 0 && left_top != -1 && grid[i][j] > grid[i - 1][j - 1] {\n                    cur = cur.max(left_top + 1);\n                }\n                \n                // Check move from direct left cell\n                if dp[i] != -1 && grid[i][j] > grid[i][j - 1] {\n                    cur = cur.max(dp[i] + 1);\n                }\n                \n                // Check move from bottom-left cell\n                if i + 1 < m && dp[i + 1] != -1 && grid[i][j] > grid[i + 1][j - 1] {\n                    cur = cur.max(dp[i + 1] + 1);\n                }\n                \n                dp[i] = cur;\n                found = found || dp[i] != -1;\n                left_top = next_left_top;\n            }\n            \n            if !found {\n                break;\n            }\n            res = j;\n        }\n        \n        res as i32\n    }\n}\n```\n```ruby []\nclass Solution\n  def max_moves(grid)\n    m = grid.length     # number of rows\n    n = grid[0].length  # number of columns\n    \n    res = 0\n    dp = Array.new(m, 0)\n    \n    (1...n).each do |j|\n      left_top = 0\n      found = false\n      \n      m.times do |i|\n        cur = -1\n        nxt_left_top = dp[i]\n        \n        # Check move from top-left cell\n        if i - 1 >= 0 && left_top != -1 && grid[i][j] > grid[i-1][j-1]\n          cur = [cur, left_top + 1].max\n        end\n        \n        # Check move from direct left cell\n        if dp[i] != -1 && grid[i][j] > grid[i][j-1]\n          cur = [cur, dp[i] + 1].max\n        end\n        \n        # Check move from bottom-left cell\n        if i + 1 < m && dp[i+1] != -1 && grid[i][j] > grid[i+1][j-1]\n          cur = [cur, dp[i+1] + 1].max\n        end\n        \n        dp[i] = cur\n        found = found || dp[i] != -1\n        left_top = nxt_left_top\n      end\n      \n      break unless found\n      res = j\n    end\n    \n    res\n  end\nend\n\n# Create an instance and call the method\ndef max_moves(grid)\n  Solution.new.max_moves(grid)\nend\n```\n## Without comments:\n```python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        m = len(grid)\n        n = len(grid[0])\n        res = 0\n        dp = [0] * m\n        \n        for j in range(1, n):\n            leftTop = 0\n            found = False\n            \n            for i in range(m):\n                cur = -1\n                nxtLeftTop = dp[i]\n                \n                if i - 1 >= 0 and leftTop != -1 and grid[i][j] > grid[i-1][j-1]:\n                    cur = max(cur, leftTop + 1)\n                \n                if dp[i] != -1 and grid[i][j] > grid[i][j-1]:\n                    cur = max(cur, dp[i] + 1)\n                \n                if i + 1 < m and dp[i+1] != -1 and grid[i][j] > grid[i+1][j-1]:\n                    cur = max(cur, dp[i+1] + 1)\n                \n                dp[i] = cur\n                found = found or (dp[i] != -1)\n                leftTop = nxtLeftTop\n            \n            if not found:\n                break\n            res = j\n        \n        return res\n```\n```cpp []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int m = grid.size();\n        int n = grid[0].size();\n        int res = 0;\n        vector<int> dp(m);\n        \n        for (int j = 1; j < n; ++j) {\n            int leftTop = 0;\n            bool found = false;\n            \n            for (int i = 0; i < m; ++i) {\n                int cur = -1;\n                int nxtLeftTop = dp[i];\n                \n                if (i - 1 >= 0 && leftTop != -1 && grid[i][j] > grid[i - 1][j - 1]) {\n                    cur = max(cur, leftTop + 1);\n                }\n                \n                if (dp[i] != -1 && grid[i][j] > grid[i][j - 1]) {\n                    cur = max(cur, dp[i] + 1);\n                }\n                \n                if (i + 1 < m && dp[i + 1] != -1 && grid[i][j] > grid[i + 1][j - 1]) {\n                    cur = max(cur, dp[i + 1] + 1);\n                }\n                \n                dp[i] = cur;\n                found = found || (dp[i] != -1);\n                leftTop = nxtLeftTop;\n            }\n            \n            if (!found) break;\n            res = j;\n        }\n        \n        return res;\n    }\n};\n```\n```java []\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int m = grid.length;\n        int n = grid[0].length;\n        int res = 0;\n        int[] dp = new int[m];\n        \n        for (int j = 1; j < n; j++) {\n            int leftTop = 0;\n            boolean found = false;\n            \n            for (int i = 0; i < m; i++) {\n                int cur = -1;\n                int nxtLeftTop = dp[i];\n                \n                if (i - 1 >= 0 && leftTop != -1 && grid[i][j] > grid[i - 1][j - 1]) {\n                    cur = Math.max(cur, leftTop + 1);\n                }\n                \n                if (dp[i] != -1 && grid[i][j] > grid[i][j - 1]) {\n                    cur = Math.max(cur, dp[i] + 1);\n                }\n                \n                if (i + 1 < m && dp[i + 1] != -1 && grid[i][j] > grid[i + 1][j - 1]) {\n                    cur = Math.max(cur, dp[i + 1] + 1);\n                }\n                \n                dp[i] = cur;\n                found = found || (dp[i] != -1);\n                leftTop = nxtLeftTop;\n            }\n            \n            if (!found) break;\n            res = j;\n        }\n        \n        return res;\n    }\n}\n```\n```csharp []\npublic class Solution {\n    public int MaxMoves(int[][] grid) {\n        int m = grid.Length;\n        int n = grid[0].Length;\n        int res = 0;\n        int[] dp = new int[m];\n        \n        for (int j = 1; j < n; j++) {\n            int leftTop = 0;\n            bool found = false;\n            \n            for (int i = 0; i < m; i++) {\n                int cur = -1;\n                int nxtLeftTop = dp[i];\n                \n                if (i - 1 >= 0 && leftTop != -1 && grid[i][j] > grid[i - 1][j - 1]) {\n                    cur = Math.Max(cur, leftTop + 1);\n                }\n                \n                if (dp[i] != -1 && grid[i][j] > grid[i][j - 1]) {\n                    cur = Math.Max(cur, dp[i] + 1);\n                }\n                \n                if (i + 1 < m && dp[i + 1] != -1 && grid[i][j] > grid[i + 1][j - 1]) {\n                    cur = Math.Max(cur, dp[i + 1] + 1);\n                }\n                \n                dp[i] = cur;\n                found = found || (dp[i] != -1);\n                leftTop = nxtLeftTop;\n            }\n            \n            if (!found) break;\n            res = j;\n        }\n        \n        return res;\n    }\n}\n```\n```golang []\nfunc maxMoves(grid [][]int) int {\n    m := len(grid)\n    n := len(grid[0]) \n    res := 0\n    dp := make([]int, m)\n    \n    for j := 1; j < n; j++ {\n        leftTop := 0\n        found := false\n        \n        for i := 0; i < m; i++ {\n            cur := -1\n            nxtLeftTop := dp[i]\n            \n            if i-1 >= 0 && leftTop != -1 && grid[i][j] > grid[i-1][j-1] {\n                cur = max(cur, leftTop+1)\n            }\n            \n            if dp[i] != -1 && grid[i][j] > grid[i][j-1] {\n                cur = max(cur, dp[i]+1)\n            }\n            \n            if i+1 < m && dp[i+1] != -1 && grid[i][j] > grid[i+1][j-1] {\n                cur = max(cur, dp[i+1]+1)\n            }\n            \n            dp[i] = cur\n            found = found || (dp[i] != -1)\n            leftTop = nxtLeftTop\n        }\n        \n        if !found {\n            break\n        }\n        res = j\n    }\n    \n    return res\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n```\n```swift []\nclass Solution {\n    func maxMoves(_ grid: [[Int]]) -> Int {\n        let m = grid.count\n        let n = grid[0].count\n        var res = 0\n        var dp = Array(repeating: 0, count: m)\n        \n        for j in 1..<n {\n            var leftTop = 0\n            var found = false\n            \n            for i in 0..<m {\n\n                var cur = -1\n                let nxtLeftTop = dp[i]\n                \n                if i - 1 >= 0 && leftTop != -1 && grid[i][j] > grid[i-1][j-1] {\n                    cur = max(cur, leftTop + 1)\n                }\n                \n                if dp[i] != -1 && grid[i][j] > grid[i][j-1] {\n                    cur = max(cur, dp[i] + 1)\n                }\n                \n                if i + 1 < m && dp[i+1] != -1 && grid[i][j] > grid[i+1][j-1] {\n                    cur = max(cur, dp[i+1] + 1)\n                }\n                \n                dp[i] = cur\n                found = found || (dp[i] != -1)\n                leftTop = nxtLeftTop\n            }\n            \n            if !found { break }\n            res = j\n        }\n        \n        return res\n    }\n}\n```\n```javascript [JS]\nvar maxMoves = function(grid) {\n    const m = grid.length; \n    const n = grid[0].length; \n    \n    let res = 0;\n    let dp = new Array(m).fill(0);\n    \n    for (let j = 1; j < n; j++) {\n        let leftTop = 0;\n        let found = false;\n        \n        for (let i = 0; i < m; i++) {\n            let cur = -1;\n            let nxtLeftTop = dp[i];\n            \n            if (i - 1 >= 0 && leftTop !== -1 && grid[i][j] > grid[i - 1][j - 1]) {\n                cur = Math.max(cur, leftTop + 1);\n            }\n            \n            if (dp[i] !== -1 && grid[i][j] > grid[i][j - 1]) {\n                cur = Math.max(cur, dp[i] + 1);\n            }\n            \n            if (i + 1 < m && dp[i + 1] !== -1 && grid[i][j] > grid[i + 1][j - 1]) {\n                cur = Math.max(cur, dp[i + 1] + 1);\n            }\n            \n            dp[i] = cur;\n            found = found || (dp[i] !== -1);\n            leftTop = nxtLeftTop;\n        }\n        \n        if (!found) break;\n        res = j;\n    }\n    \n    return res;\n};\n```\n```typescript [TS]\nfunction maxMoves(grid: number[][]): number {\n    const m: number = grid.length;    \n    const n: number = grid[0].length; \n    \n    let res: number = 0;\n    let dp: number[] = new Array(m).fill(0);\n    \n    for (let j = 1; j < n; j++) {\n        let leftTop: number = 0;\n        let found: boolean = false;\n        \n        for (let i = 0; i < m; i++) {\n            let cur: number = -1;\n            let nxtLeftTop: number = dp[i];\n            \n            if (i - 1 >= 0 && leftTop !== -1 && grid[i][j] > grid[i - 1][j - 1]) {\n                cur = Math.max(cur, leftTop + 1);\n            }\n            \n            if (dp[i] !== -1 && grid[i][j] > grid[i][j - 1]) {\n                cur = Math.max(cur, dp[i] + 1);\n            }\n            \n            if (i + 1 < m && dp[i + 1] !== -1 && grid[i][j] > grid[i + 1][j - 1]) {\n                cur = Math.max(cur, dp[i + 1] + 1);\n            }\n            \n            dp[i] = cur;\n            found = found || (dp[i] !== -1);\n            leftTop = nxtLeftTop;\n        }\n        \n        if (!found) break;\n        res = j;\n    }\n    \n    return res;\n}\n```\n```rust []\nimpl Solution {\n    pub fn max_moves(grid: Vec<Vec<i32>>) -> i32 {\n        let m = grid.len();    \n        let n = grid[0].len(); \n        \n        let mut res = 0;\n        let mut dp = vec![0; m];\n        \n        for j in 1..n {\n            let mut left_top = 0;\n            let mut found = false;\n            \n            for i in 0..m {\n                let mut cur = -1;\n                let next_left_top = dp[i];\n                \n                if i > 0 && left_top != -1 && grid[i][j] > grid[i - 1][j - 1] {\n                    cur = cur.max(left_top + 1);\n                }\n                \n                if dp[i] != -1 && grid[i][j] > grid[i][j - 1] {\n                    cur = cur.max(dp[i] + 1);\n                }\n                \n                if i + 1 < m && dp[i + 1] != -1 && grid[i][j] > grid[i + 1][j - 1] {\n                    cur = cur.max(dp[i + 1] + 1);\n                }\n                \n                dp[i] = cur;\n                found = found || dp[i] != -1;\n                left_top = next_left_top;\n            }\n            \n            if !found {\n                break;\n            }\n            res = j;\n        }\n        \n        res as i32\n    }\n}\n```\n```ruby []\nclass Solution\n  def max_moves(grid)\n    m = grid.length \n    n = grid[0].length \n    \n    res = 0\n    dp = Array.new(m, 0)\n    \n    (1...n).each do |j|\n      left_top = 0\n      found = false\n      \n      m.times do |i|\n        cur = -1\n        nxt_left_top = dp[i]\n        \n        if i - 1 >= 0 && left_top != -1 && grid[i][j] > grid[i-1][j-1]\n          cur = [cur, left_top + 1].max\n        end\n        \n        if dp[i] != -1 && grid[i][j] > grid[i][j-1]\n          cur = [cur, dp[i] + 1].max\n        end\n        \n        if i + 1 < m && dp[i+1] != -1 && grid[i][j] > grid[i+1][j-1]\n          cur = [cur, dp[i+1] + 1].max\n        end\n        \n        dp[i] = cur\n        found = found || dp[i] != -1\n        left_top = nxt_left_top\n      end\n      \n      break unless found\n      res = j\n    end\n    \n    res\n  end\nend\n\ndef max_moves(grid)\n  Solution.new.max_moves(grid)\nend\n```\n\n![image.png](https://assets.leetcode.com/users/images/9dc1b265-b175-4bf4-bc6c-4b188cb79220_1728176037.4402142.png)\n\n### Complexity \n- Time complexity: O(m * n)\n\n- Space complexity: O(m)\n\n# Most common Interview Matrix Problems\n\n\nFrom the most to the least common  (from GitHub/reddit):\n\n[[54. Spiral Matrix]](https://leetcode.com/problems/spiral-matrix/description/) [[48. Rotate Image]](https://leetcode.com/problems/rotate-image/description/)  [[73. Set Matrix Zeroes]](https://leetcode.com/problems/set-matrix-zeroes/description/) [[240. Search a 2D Matrix II]](https://leetcode.com/problems/set-matrix-zeroes/description/)  [[329. Longest Increasing Path in a Matrix]](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/) [[1252. Cells with Odd Values in a Matrix]](https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/description/)\n\n![image.png](https://assets.leetcode.com/users/images/fe4c6527-44df-4ef0-8dd7-3b0ad39f2dc3_1730168198.6890616.png)\n\n# Matrix BFS Template\n\n```python3 []\nnum_rows, num_cols = len(grid), len(grid[0])\ndef get_neighbors(coord):\n    row, col = coord\n    delta_row = [-1, 0, 1, 0]\n    delta_col = [0, 1, 0, -1]\n    res = []\n    for i in range(len(delta_row)):\n        neighbor_row = row + delta_row[i]\n        neighbor_col = col + delta_col[i]\n        if 0 <= neighbor_row < num_rows and 0 <= neighbor_col < num_cols:\n            res.append((neighbor_row, neighbor_col))\n    return res\n\nfrom collections import deque\n\ndef bfs(starting_node):\n    queue = deque([starting_node])\n    visited = set([starting_node])\n    while len(queue) > 0:\n        node = queue.popleft()\n        for neighbor in get_neighbors(node):\n            if neighbor in visited:\n                continue\n            # Do stuff with the node if required\n            # ...\n            queue.append(neighbor)\n            visited.add(neighbor)\n\n```\n```cpp []\nint num_rows = grid.size();\nint num_cols = grid[0].size();\n\nstd::vector<Coordinate> get_neighbors(Coordinate coord) {\n    int row = coord.row;\n    int col = coord.col;\n    int delta_row[4] = {-1, 0, 1, 0};\n    int delta_col[4] = {0, 1, 0, -1};\n    std::vector<Coordinate> res;\n    for (int i = 0; i < 4; i++) {\n        int neighbor_row = row + delta_row[i];\n        int neighbor_col = col + delta_col[i];\n\n        if (0 <= neighbor_row && neighbor_row < num_rows &&\n        0 <= neighbor_col && neighbor_col < num_cols) {\n            res.emplace_back(Coordinate(neighbor_row, neighbor_col));\n        }\n    }\n    return res;\n}\n\nvoid bfs(Coordinate starting_node) {\n    std::queue<Coordinate> q;\n    q.push(starting_node);\n    std::unordered_set<Coordinate> visited;\n    visited.emplace(starting_node);\n\n    while (q.size() > 0) {\n        Coordinate node = q.front();\n        for (Coordinate neighbor : get_neighbors(node)) {\n            if (visited.count(neighbor)) continue;\n            // Do stuff with the node if required\n            // ...\n            q.push(neighbor);\n            visited.emplace(neighbor);\n        }\n        q.pop();\n    }\n}\n\n```\n```java []\npublic int numRows = grid.length;\npublic int numCols = grid[0].length;\n\npublic List<Coordinate> getNeighbors(Coordinate coord) {\n    int row = coord.row;\n    int col = coord.col;\n    int[] deltaRow = {-1, 0, 1, 0};\n    int[] deltaCol = {0, 1, 0, -1};\n    List<Coordinate> res = new ArrayList<>();\n    for (int i = 0; i < deltaRow.length; i++) {\n        int neighborRow = row + deltaRow[i];\n        int neighborCol = col + deltaCol[i];\n        if (0 <= neighborRow && neighborRow < numRows &&\n            0 <= neighborCol && neighborCol < numCols) {\n                res.add(new Coordinate(neighborRow, neighborCol));\n            }\n    }\n    return res;\n}\n\npublic void bfs(Coordinate startingNode) {\n    Deque<Coordinate> queue = new ArrayDeque<>();\n    queue.add(startingNode);\n    Set<Coordinate> visited = new HashSet<>();\n    visited.add(startingNode);\n\n    while (queue.size() > 0) {\n        Coordinate node = queue.pop();\n        for (Coordinate neighbor : getNeighbors(node)) {\n            if (visited.contains(neighbor)) continue;\n            // Do stuff with the node if required\n            // ...\n            queue.add(neighbor);\n            visited.add(neighbor);\n        }\n    }\n}\n\n```\n```csharp []\npublic static int numRows = grid.Count;\npublic static int numCols = grid[0].Count;\n\npublic static List<Coordinate> GetNeighbors(Coordinate coord)\n{\n    int row = coord.row;\n    int col = coord.col;\n    int[] deltaRow = {-1, 0, 1, 0};\n    int[] deltaCol = {0, 1, 0, -1};\n    List<Coordinate> res = new List<Coordinate>();\n    for (int i = 0; i < deltaRow.Length; i++)\n    {\n        int neighborRow = row + deltaRow[i];\n        int neighborCol = col + deltaCol[i];\n        if (0 <= neighborRow && neighborRow < numRows &&\n        0 <= neighborCol && neighborCol < numCols)\n        {\n            res.Add(new Coordinate(neighborRow, neighborCol));\n        }\n    }\n    return res;\n}\n\npublic static void Bfs(Coordinate startingNode)\n{\n    Queue<Coordinate> queue = new Queue<Coordinate>();\n    queue.Enqueue(startingNode);\n    HashSet<Coordinate> visited = new HashSet<Coordinate>();\n    visited.Add(startingNode);\n    while (queue.Count > 0)\n    {\n        Coordinate node = queue.Dequeue();\n        foreach (Coordinate neighbor in GetNeighbors(node))\n        {\n            if (visited.Contains(neighbor)) continue;\n            // Do stuff with the node if required\n            // ...\n            queue.Enqueue(neighbor);\n            visited.Add(neighbor);\n        }\n    }\n}\n\n```\n```javascript []\nnum_rows = grid.length;\nnum_cols = grid[0].length;\n\nfunction get_neighbors(coord) {\n    const [row, col] = coord;\n    const delta_row = [-1, 0, 1, 0];\n    const delta_col = [0, 1, 0, -1];\n    const res = [];\n    for (let i = 0; i < delta_row.length; i++) {\n        neighbor_row = row + delta_row[i];\n        neighbor_col = col + delta_col[i];\n        if (0 <= neighbor_row && neighbor_row < num_rows &&\n          0 <= neighbor_col && neighbor_col < num_cols) {\n              res.push([neighbor_row, neighbor_col]);\n          }\n    }\n    return res;\n}\n\nfunction bfs(starting_node) {\n    const queue = [starting_node];\n    const visited = new Set([starting_node]);\n    while (queue.length > 0) {\n        const node = queue.shift();\n        for (const neighbor of get_neighbors(node)) {\n            if (visited.has(neighbor)) continue;\n            // Do stuff with the node if required\n            // ...\n            queue.push(neighbor);\n            visited.add(neighbor);\n        }\n    }\n}\n\n```\n# Explanation\n\n---\n![image.png](https://assets.leetcode.com/users/images/bac7f511-80ba-47fc-adbc-e0a5a1202cc3_1730167226.8547862.png)\n## 1. Understanding\n\n- We have a grid where we can start from any cell in the first column\n- From each cell, we can move diagonally up-right, right, or diagonally down-right\n- We can only move to cells with strictly larger values\n- Goal: Find maximum possible moves\n\n## 2. Approach\n\n- Use dynamic programming to track reachable cells\n- Process the grid column by column\n- For each cell, check if we can reach it from previous column\n\n## 3. Algorithm:\n\n- For each column j (starting from 1):\n    - For each row i:\n        - Check three possible moves: a. From top-left (i-1, j-1) b. From left (i, j-1) c. From bottom-left (i+1, j-1)\n        - Update dp[i] with maximum possible moves\n\n## 4. Details\n\n- Use leftTop variable to track previous diagonal value\n- Use found flag to check if current column is reachable\n- Break if no cell in current column is reachable\n\n## 5. Optimalization\n\n- Only store one column of dp values at a time\n- Early termination when no cells are reachable\n- Efficient tracking of diagonal values\n\n---\n\n\n![image.png](https://assets.leetcode.com/users/images/c99ef61e-33c1-4de5-89dd-7a16063205be_1730160722.2846944.png)\n![image.png](https://assets.leetcode.com/users/images/01c7b886-98ba-4b76-ad82-8812135ffe14_1730160925.2726061.png)\n![image.png](https://assets.leetcode.com/users/images/f950a0d7-3af7-4b69-9858-0d86373dfe37_1730167414.1770644.png)\n\n
['Swift', 'C++', 'Java', 'Go', 'TypeScript', 'Python3', 'Rust', 'Ruby', 'JavaScript', 'C#']