simple iterative solution | without DP | well commented | C++
Intuition\n Describe your first thoughts on how to solve this problem. \nWhat I understood from the question is that:\n- I have to start from the 0th column, an
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhat I understood from the question is that:\n- I have to start from the 0th column, and have to go till the last column.\n- I can can move to any of the three cells from (row, col) : (row - 1, col + 1), (row, col + 1) and (row + 1, col + 1).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- need a data structure to efficiently store and access element of int type.\n- start from 0th col and will store all elements, and then will iterate to the remaining cols and will store the valid next rows in the data structure.\n- will try to go to the last column, and will return the column value if can\'t go to the next columns\n\n# Complexity\n- Time complexity: $$O(m*n)$$\n- Space complexity: $$O(m*n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n- m --> rows\n- n --> cols\n- SC can be improved further without creating temp.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        \n        unordered_set<int> st;\n        for(int i = 0; i < m; i++) { // for 0th col\n            if(i-1 >= 0 && grid[i-1][1] > grid[i][0]) st.insert(i-1);\n            if(grid[i][1] > grid[i][0]) st.insert(i);\n            if(i+1 < m && grid[i+1][1] > grid[i][0]) st.insert(i+1);\n        }\n        if(st.empty()) return 0; // IMP edge case\n\n        int j = 1;\n        for(j = 1; j < n; j++) { // for rest cols\n            unordered_set<int> temp; // new container to store next set of valid rows\n            for(int i : st) {\n                if(i-1 >= 0 && j+1 < n && grid[i-1][j+1] > grid[i][j]) temp.insert(i-1);\n                if(j+1 < n && grid[i][j+1] > grid[i][j]) temp.insert(i);\n                if(i+1 < m && j+1 < n && grid[i+1][j+1] > grid[i][j]) temp.insert(i+1);\n            }\n            if(temp.empty()) break;\n            st = move(temp);\n        }\n\n        return j;\n    }\n};\n\n```
['Array', 'Matrix', 'C++']