100% - hardcore DP action
Intuition\nThis is all about finding when you run out of moves, which is equivalent to finding out what previous moves were available to get here.\n\n# Approach
# Intuition\nThis is all about finding when you run out of moves, which is equivalent to finding out what previous moves were available to get here.\n\n# Approach\nIf we start on column 1, we can look at the previous columns and find which row values were less than this one. If none of them are, then we no longer care if any values in the next one are greater than this one because this value can\'t be reached in the first place. I mark this by updating an unreachable value to `i32::MAX`, which ensures that the next column also won\'t have any numbers reachable from there. We carry on like this and return early if every previous number was unreachable.\n\nI considered having it narrow the indexes we check on the next one. However that would require tracking all this extra data to link the path. That\'s almost always going to perform worse than what I have, which is a simple iteration through a Vec that\'s accessed by index, which is incredibly fast and cpu-optimized. My approach will always do an m*n scan of all elements, but the check is very lightweight.\n\n# Complexity\n- Time complexity:\n$$O(n * m )$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```rust []\nimpl Solution {\n    pub fn max_moves(mut grid: Vec<Vec<i32>>) -> i32 {\n        let w = grid[0].len();\n        let h = grid.len();\n        // Start 1 column in since we only look backwards\n        for col in 1..w {\n            let mut missed = 0;\n            // Check each row in the column to see if it\'s reachable\n            for row in 0..h {\n                let v = grid[row][col];\n                if !(v > grid[row][col - 1]\n                    || (row > 0 && v > grid[row - 1][col - 1])\n                    || (row < (h - 1) && v > grid[row + 1][col - 1]))\n                {\n                    grid[row][col] = i32::MAX;\n                    missed += 1;\n                }\n            }\n            // If none were reached, this is the max length.\n            if missed == h {\n                return col as i32 - 1;\n            }\n        }\n        w as i32 - 1\n    }\n}\n\n```\n```python []\n# 31ms runtime. Beats 100% runtime and memory.\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        w = len(grid[0])\n        h = len(grid)\n        for col in range(1, w):\n            missed = 0\n            for row in range(h):\n                v = grid[row][col]\n                if not (v > grid[row][col - 1] or \n                        (row > 0 and v > grid[row - 1][col - 1]) or \n                        (row < h - 1 and v > grid[row + 1][col - 1])):\n                    grid[row][col] = float(\'inf\')\n                    missed += 1\n            if missed == h:\n                return col - 1\n        return w - 1\n```\n```typescript []\n// 5ms. Beats 100% of both.\nfunction maxMoves(grid: number[][]): number {\n    const w = grid[0].length;\n    const h = grid.length;\n\n    for (let col = 1; col < w; col++) {\n        let missed = 0;\n        for (let row = 0; row < h; row++) {\n            const v = grid[row][col];\n            if (!(v > grid[row][col - 1] || \n                  (row > 0 && v > grid[row - 1][col - 1]) || \n                  (row < h - 1 && v > grid[row + 1][col - 1]))) {\n                grid[row][col] = Infinity;\n                missed += 1;\n            }\n        }\n        if (missed === h) {\n            return col - 1;\n        }\n    }\n    return w - 1;\n}\n```
['Array', 'Dynamic Programming', 'TypeScript', 'Python3', 'Rust']