Efficient Solution for Rotating and Simulating Gravity in a Box (C++ | O(n * m) Time Complexity)
Intuition\nThe problem involves simulating a "falling stones" effect and rotating the box (2D grid) 90 degrees clockwise. The key insights are:\n\n1. Simulating
# Intuition\nThe problem involves simulating a "falling stones" effect and rotating the box (2D grid) 90 degrees clockwise. The key insights are:\n\n1. Simulating Gravity:\n- Each stone (#) should fall to the lowest possible position in its row, stopping when it encounters either a wall (*) or another stone.\n- This behavior is processed row by row.\n2. Rotation:\n- Convert columns of the original box into rows of the rotated box.\n- Reverse the order of the rows to achieve the correct orientation.\n- By handling these steps separately, the task becomes more manageable.\n# Approach\n1. Adjust the Stones in Each Row:\n- For each row, iterate backward (right to left) to simulate gravity:\n- Use a pointer to track the nearest empty cell (.) where a stone can fall.\n- If a stone (#) is found, move it to the empty cell and update the pointer.\n- Skip walls (*) as they block stones from falling beyond them.\n2. Rotate the Box:\n- Create a new matrix ans to represent the rotated box.\n- For each cell in the original box, determine its corresponding position in the rotated box:\n- The row index in the rotated box becomes the column index in the original box.\n- The column index in the rotated box is the reverse of the row index in the original box.\n3. Return the Rotated Box:\n- The final result is the rotated version of the box after simulating the stone-falling effect.\n# Complexity\n- Time complexity: O(n\u22C5m).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n\u22C5m).\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {\n        int n = box.size();\n        int m = box[0].size();\n        \n        // Adjust stones in the box row-wise\n        for (int i = 0; i < n; i++) {\n            for (int j = m - 1; j >= 0; j--) {\n                if (box[i][j] == \'*\' || box[i][j] == \'.\') continue;\n                else {\n                    int a = j + 1;\n                    while (a < m && box[i][a] == \'.\') {\n                        a++;\n                    }\n                    swap(box[i][j], box[i][a - 1]); // Swap with the last empty cell\n                }\n            }\n        }\n        \n        // Rotate the box by transposing and reversing\n        vector<vector<char>> ans(m, vector<char>(n, \'.\'));\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                ans[j][n - 1 - i] = box[i][j];\n            }\n        }\n        \n        return ans;\n    }\n};\n\n```
['Array', 'Two Pointers', 'Matrix', 'C++']