Iteration and O(1) Extra Space | C++, Python, Java
Intuition\n Describe your first thoughts on how to solve this problem. \nA DFS came to mind but I felt this could be solved without it and this is what i came u
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nA DFS came to mind but I felt this could be solved without it and this is what i came up with. Got 3 ms on my submission.\n\nWe iterate column by column and mark values that were reachable by setting them to negative values (since `grid[i][j] >= 1`). On each iteration for each column, we set mark all the reachable values in that column. At any `grid[i][j]`, it is reachable if it is greater than `grid[i][j-1]`, `grid[i-1][j-1]`, or `grid[i+1][j-1]` (and either of them is reachable).\n\nThis way we can efficiently see how far we can get and break out the loop early if there was no reachable values from a given column. Additionally, we firstly mark all the values in the first column as reachable since we can start from any value in it.\n\nMarking the values as negative helps us bring the extra space required down to $$O(1)$$ since we don\'t use extra space to store previous values, mark values, BFS, or for recursive DFS.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(mn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        for (int i = 0; i < m; i++)\n            grid[i][0] = -grid[i][0];\n        int res = 0, moves[3][2] = {{0, -1}, {-1, -1}, {1, -1}};\n        for (int c = 1; c < n; c++){\n            bool found = false;\n            for (int r = 0; r < m; r++){\n                for (auto& move : moves){\n                    int dr = r + move[0], dc = c + move[1];\n                    if (dr >= 0 && dr < m && dc >= 0 && dc < n){\n                        if (grid[dr][dc] < 0 && grid[r][c] > -grid[dr][dc]){\n                            found = true;\n                            grid[r][c] = -grid[r][c];\n                            break;\n                        }\n                    }\n                }\n            }\n            if (found) res++;\n            else break;\n        }\n        return res;\n    }\n};\n```\n```python []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        m, n = len(grid), len(grid[0])\n        for i in range(m):\n            grid[i][0] = -grid[i][0]\n        res, moves = 0, [[0, -1], [-1, -1], [1, -1]]\n        for c in range(1, n):\n            found = False\n            for r in range(m):\n                for move in moves:\n                    dr, dc = r + move[0], c + move[1]\n                    if 0 <= dr < m and 0 <= dc < n:\n                        if grid[dr][dc] < 0 and grid[r][c] > -grid[dr][dc]:\n                            found = True\n                            grid[r][c] = -grid[r][c]\n                            break\n            if found: res += 1\n            else: break\n        return res\n```\n```Java []\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int m = grid.length, n = grid[0].length;\n        for (int i = 0; i < m; i++)\n            grid[i][0] = -grid[i][0];\n        int res = 0;\n        int[][] moves = {{0, -1}, {-1, -1}, {1, -1}};\n        for (int c = 1; c < n; c++){\n            boolean found = false;\n            for (int r = 0; r < m; r++){\n                for (int[] move : moves){\n                    int dr = r + move[0], dc = c + move[1];\n                    if (dr >= 0 && dr < m && dc >= 0 && dc < n){\n                        if (grid[dr][dc] < 0 && grid[r][c] > -grid[dr][dc]){\n                            found = true;\n                            grid[r][c] = -grid[r][c];\n                            break;\n                        }\n                    }\n                }\n            }\n            if (found) res++;\n            else break;\n        }\n        return res;\n    }\n}\n```\n
['Array', 'Dynamic Programming', 'C', 'Matrix', 'Python', 'C++', 'Java', 'Python3']