Given an NxN array, rotate it 90 degrees without making a new array
Given An n x n Array Rotate It 90 Degrees Without Making A New Array
Oh boy, matrix operations, isn't that fun?
This problem seems to require some visualization first, so I'll grab my pen and I'll start drawing stuff before trying to implement it, will that help? (I'm writing this post after figuring it out, so I guess it did! ¯\_(ツ)_/¯)
Looking for the simplest case (n=2)
In this matrix (2x2) we need to make 4 operations:
- Top-Left → Top-Right
- Bottom-Left → Top-Left
- Bottom-Right → Bottom-Left
- Top-Right → Bottom-Right
Sounds easy, but what happens when we have more?
We can imagine our matrices as compositions of rings, and we need to rotate every ring individually
For the example given, we just need to rotate the external ring, and the
5 in the middle stays as it is.
It gets more interesting when we have a higher
n = 4 we have to rotate 2 rings, and the number of rings increases with every 2 increments in
n (we can probably say that number of rings =
n / 2).
Rotating a ring, general case.
Let's try to extract the general rule for rotating an individual ring, I'll use a higher
n for that, since it was difficult to extract it from the simplest case:
We need to traverse all the positions - 1 inside a ring and make the move operations. The exact operations depend on the movement, and we need to keep one item in memory since it will be overriden after one of the operations.
This is the operation for
We need to write similar operations for the other movements.
This should do the trick, I have to confess that I needed to implement tests to ensure I didn't mess up with the movement operations (TDD FTW!).
Big-O complexity for this one should be something like
O(n / 2 * n / 2) ->
O(n^2) although I'm not completely sure if this is correct... so we can leave it as trust me, this is fine :D