O(1) Space ACED BOTH✅THE FASTEST✅100% || 0ms🔥100% || 66.65MB🚀✅⚡️
\n\n---\n\n# Approach :\n Describe your first thoughts on how to solve this problem. \n###### We need to know at each column up until which index is the path op
![image.png](https://assets.leetcode.com/users/images/f567d7f7-15c5-4d3e-87f4-038d5e287451_1730226157.0656939.png)\n\n---\n\n# Approach :\n<!-- Describe your first thoughts on how to solve this problem. -->\n###### We need to know at each column up until which index is the path open. We could use for instance unordered_map or something like unordered_set to store already covered paths. BUT We can make the number that is the last one known on a path equal to the opposite of the value(`for instance if path ends on 5 we make it -5 and thus know on next iteration that negative numbers hold paths`).\n###### now, if we have 3 ways to go from one tile, we can look at the problem at a one step ahead view and say that we can get to a single tile by 3 tiles that are in previous column.(`thus, we need to turn all numbers in the first column to their opposites as we know that they are starting points of paths`) Start the main problem logic(`like comparing is current is strictly higher than -(previous 3 tiles on i - 1, i and i + 1 rows and j - 1 column) (\'-\' sign is crucial there as we need number\'s original value)`) form column 1 forward.\n---\n\n# Complexity :\n- Time complexity: $O(n * m)$\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```cpp [Yippee || C++ || very happy that i came up with this sol on my own xd. keep pushing  and learning\uD83D\uDE80 that\'s the way!]\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);\n        for(int i = 0; i < grid.size(); ++i) {\n            grid[i][0] *= -1;\n        }\n\n        int maxMoves = 0;\n        for(int j = 1; j < grid[0].size(); ++j) {\n            bool atLeastOnePath = false;\n            for(int i = 0; i < grid.size(); ++i) {\n                if((i != 0 && grid[i - 1][j - 1] < 0 && -grid[i - 1][j - 1] < grid[i][j]) || \n                    (grid[i][j - 1] < 0 && -grid[i][j - 1] < grid[i][j]) || \n                    (i != grid.size() - 1 && grid[i + 1][j - 1] < 0 && -grid[i + 1][j - 1] < grid[i][j])) {\n                    \n                    // body of the condition\n                    grid[i][j] *= -1;\n                    atLeastOnePath = true;\n                }\n            }\n            if(!atLeastOnePath) {\n                break;\n            }\n            ++maxMoves;\n        }\n        return maxMoves;\n    }\n};\n```
['Array', 'Dynamic Programming', 'Matrix', 'C++']