0

This is a pretty famous question where you need to rotate the matrix 90 degrees counter clockwise around the center element. What i don't understand is the smart solution to this problem, which first takes the transpose of the matrix first and then reverse the elements in each column. Can anybody provide the intuition behind this, or prove why this works.

Link: https://www.geeksforgeeks.org/rotate-matrix-90-degree-without-using-extra-space-set-2/

Olivier
  • 13,283
  • 1
  • 8
  • 24
dark_prince
  • 237
  • 2
  • 12
  • 3
    Take a book or piece of paper and flip it horizontally (left-right), then hold it on top left and bottom right corner and flip it over again, the book should be rotated counter clockwise 90 degrees. – jackw11111 Jul 11 '21 at 09:16
  • any link on the "famous question" & the "smart solution" ? – p._phidot_ Jul 11 '21 at 09:20
  • @p._phidot_ link added. – dark_prince Jul 11 '21 at 09:40
  • FYI you can effectively accomplish the same thing in O(1) time & space by leaving the matrix unchanged and transforming the cell coordinates to match the matrix rotation. – Dave Jul 11 '21 at 14:54
  • @Dave yes i know that, but i didn't understand the linked solution.(using transpose and reverse). – dark_prince Jul 11 '21 at 15:50

1 Answers1

1

Transposition can be seen as a reflection through the top-left / bottom-right axis.

Reversing elements in columns can be seen as a reflection through the middle horizontal axis.

When you compose two reflections with axis that make an angle of theta, you get a rotation of 2 * theta, as explained here:

A rotation in the plane can be formed by composing a pair of reflections. First reflect a point P to its image P′ on the other side of line L1. Then reflect P′ to its image P′′ on the other side of line L2. If lines L1 and L2 make an angle θ with one another, then points P and P′′ will make an angle 2θ around point O, the intersection of L1 and L2.

Here L1 and L2 make an angle of 45°, so you get a rotation of 90°.

Olivier
  • 13,283
  • 1
  • 8
  • 24
  • 1
    That's a Missy Elliott rotation: https://stackoverflow.com/questions/67275505/in-accordance-with-missy-elliotts-song-work-it-what-data-structures-can-be-bot/67275679#67275679 – Matt Timmermans Jul 11 '21 at 22:13