Daily bit(e) of C++ | Rotating a matrix
Daily bit(e) of C++ #196, Common interview problem: In-place rotation of a matrix by 90°.
Today we will look at a common C++ interview problem: In-place rotating a matrix by 90°.
Given a square matrix as std::vector<std::vector<int>>, mutate the matrix so that its content is rotated clockwise around the centre by 90°. You can only use O(1) additional memory.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/1Kccj84sE.
Solution
Because we are rotating around the centre, we effectively create groups of four elements that will swap positions with each other.
Arriving at the specific formula for these elements is easiest if you draw an example, after which you should have the following indices:
matrix[row][col]
matrix[size-1-col][row]
matrix[size-1-row][size-1-col]
matrix[col][size-1-row]
We can circularly swap these elements using a temporary variable and a sequence of assignments, or we can use the std::exchange utility, which assigns a new value to a variable, after which it returns the original value.
Finally, we only want to rotate once, meaning we must only iterate over one matrix quadrant. However, we need to be careful with odd-sized matrices; since, for an odd-sized matrix, the quadrant is a rectangle.
