122 ms beats 100%. Further improvement upon my solution from yesterday
\n# Note\nThis is further improvement upon my solution from yesterday, which can be found at https://leetcode.com/problems/rotating-the-box/solutions/6073547/hi
![Screenshot 2024-11-23 074800.jpg](https://assets.leetcode.com/users/images/b9c98714-e8aa-4f55-ab2c-31bc3de9038a_1732373505.9444966.jpeg)\n# Note\nThis is further improvement upon my solution from yesterday, which can be found at https://leetcode.com/problems/rotating-the-box/solutions/6073547/highly-optimized-solution-142-ms/.\n\n# Request\nIf you find the solution below helpful, please upvote. Your upvote is my only way of knowing what to focus on in the future.\n\n# Intuition\n- This solution is only slightly different from my solution from yesterday. For a full description of the solution, please follow the link above to yesterday\'s solution.\n- The only change is that instead of searching for the next stone or obstacle, the index of the next stone or obstacle is memoized.\n- Columns are traversed from last to first, so maintaining the next (i.e. closest higher-column index) stone or obstacle doesn\'t require any additional traversal.\n- The impact of this further optimization is a reduction of the total run-time from 142 ms yesterday, to **122 ms which at the time of writing beats 100%**.\n\n# Complexity\n- Time complexity: $$O(M*N)$$.\n- Space complexity: $$O(M*N)$$ for non-square matrices, or $$O(1)$$ for square matrices.\n\n# Code\n```cpp []\nclass Solution\n{\npublic:\n    // rotateTheBox - stub provided by LeetCode.\n    vector<vector<char>> rotateTheBox(vector<vector<char>> &box)\n    {\n        // Base case - matrix size 1x1.\n        if (box.size() == 1ul && box.front().size() == 1ul)\n            return box;\n\n        // Go over rows.\n        size_t row;\n        int    col;\n        size_t nextStoneOrObstacle;\n        for (row = 0ul; row != box.size(); ++row)\n        {\n            // Go over columns from last to first.\n            nextStoneOrObstacle = box.front().size();\n            for (col = box.front().size()-1ul; col != -1; --col)\n                switch (box[row][col])\n                {\n                case \'#\':\n                    // Move stone to just before next obstacle or other stone.\n                    box[row][col] = \'.\';\n                    box[row][--nextStoneOrObstacle] = \'#\';\n                    break;\n                case \'*\':\n                    // Encountered obstacle - this is now the next obstacle or\n                    // stone.\n                    nextStoneOrObstacle = col;\n                }\n        }\n\n        // Rotate matrix clockwise.\n        const size_t rowsMinus1 = box.size()-1ul;\n        if (box.size() == box.front().size())\n        {\n            // Square matrix - rotate inplace by mirroring lines and transposing.\n            const size_t halfRows = box.size() >> 1ul;\n            for (row = 0ul; row != halfRows; ++row)\n                box[row].swap(box[rowsMinus1-row]);\n            for (row = 1ul; row != box.size(); ++row)\n                for (col = 0; col != row; ++col)\n                    swap(box[col][row], box[row][col]);\n            return box;\n        }\n\n        // Non-square matrix - create new rotated matrix.\n        vector<vector<char>> result(box.front().size(),\n                                    vector<char>(box.size()));\n        for (row = 0ul; row != box.size(); ++row)\n            for (col = 0; col != box.front().size(); ++col)\n                result[col][rowsMinus1 - row] = box[row][col];\n        return result;\n    }\n};\n\nstatic const int speedup = []()\n{\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return 0;\n}();\n\n```
['C++']