Rotate The Matrix

Easy
0/40
profile
Contributed by
100 upvotes

Problem statement

You are given a square matrix ‘Mat’ of size ‘N’. You need to rotate ‘Mat’ by 90 degrees in the clockwise direction.

Note:

You must rotate the matrix in place, i.e., you must modify the given matrix itself. You must not allocate another square matrix for rotation.

For example

When,
‘N’ = 2 and ‘Mat’ = {{1, 2}, {3, 4}}, we must modify ‘Mat’ to {{3, 1}, {4, 2}}.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘N’, denoting the size of the matrix ‘Mat’.
Next ‘N’ lines contain ‘N’ integers each, denoting a row of ‘Mat’.
Output Format: 
You must modify the given matrix ‘Mat’, such that it is rotated in the clockwise direction by 90 degrees.
Constraints: 
1 <= N <= 100
1 <= Mat[i][j] <= 10^9

Time Limit: 1 sec
Hint

Try to simulate the rotation process.

Approaches (2)
Simulating Rotation:

Approach:

  • We can look at the matrix as multiple square rings containing rings of smaller sizes inside them. For an element of a particular ring of size ‘X’, the destination of any element of that ring is at a distance of ‘X - 1’ units on that ring in the clockwise direction.
https://files.codingninjas.in/rings-21687.png
  • Likewise, for each side of the ring, we get a cycle of four elements that want to take their neighbour’s position in the clockwise direction. This can be simulated elegantly by performing three swaps in the anti-clockwise direction.
https://files.codingninjas.in/cycle_in_a_ring-21686.png
  • We perform such swaps for all cycles in all rings. Lastly, we return the updated matrix.

 

Algorithm:

  • Start = 0
  • End = N - 1
  • while(End > Start):
    • For ‘i’ from ‘Start’ to ‘End - 1’:
      • swap(Mat[Start][i], Mat[End - i + Start][Start])
      • swap(Mat[End - i + Start][Start], Mat[End][End - i + Start])
      • swap(Mat[End][End - i + Start], Mat[i][End])
    • End = End - 1
    • Start = Start + 1
Time Complexity

O(N * N), where ‘N’ is the size of ‘Mat’.

 

We are traversing through the entire matrix, which takes O(N * N) time and the swap operations take O(1) time. Hence, the overall time complexity of this solution is O(N * N).

Space Complexity

O(1)

 

Since we are not allocating any extra space anywhere, the overall space complexity of this solution is O(1).

Code Solution
(100% EXP penalty)
Rotate The Matrix
Full screen
Console