Given a square matrix, turn it by 90 degrees in an anti-clockwise direction without using any extra space
Examples:
Input:
Matrix: 1 2 3
4 5 6
7 8 9Output: 3 6 9
2 5 8
1 4 7Input:
Matrix: 1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16Output: 4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
Note: An approach that requires extra space is already discussed here.
Example no1 – Inplace rotate square matrix by 90 degrees by forming cycles:
To solve the problem follow the below idea:
To solve the question without any extra space, rotate the array in form of squares, dividing the matrix into squares or cycles. For example,
A 4 X 4 matrix will have 2 cycles. The first cycle is formed by its 1st row, last column, last row, and 1st column. The second cycle is formed by the 2nd row, second-last column, second-last row, and 2nd column. The idea is for each square cycle, to swap the elements involved with the corresponding cell in the matrix in an anti-clockwise direction i.e. from top to left, left to bottom, bottom to right, and from right to top one at a time using nothing but a temporary variable to achieve this
Dry run of the above approach:
First Cycle:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16Moving first group of four elements (elements
of 1st row, last row, 1st column and last column) of first cycle
in counter clockwise.4 2 3 16
5 6 7 8
9 10 11 12
1 14 15 13Moving next group of four elements of
first cycle in counter clockwise4 8 3 16
5 6 7 15
2 10 11 12
1 14 9 13Moving final group of four elements of
first cycle in counter clockwise4 8 12 16
3 6 7 15
2 10 11 14
1 5 9 13Second Cycle:
4 8 12 16
3 6 7 15
2 10 11 14
1 5 9 13Fixing second cycle
4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
Follow the given steps to solve the problem:
- There are N/2 squares or cycles in a matrix of side N. Process a square one at a time. Run a loop to traverse the matrix a cycle at a time, i.e loop from 0 to N/2 – 1, loop counter is i
- Consider elements in group of 4 in current square, rotate the 4 elements at a time. So the number of such groups in a cycle is N – 2*i.
- So run a loop in each cycle from x to N – x – 1, loop counter is y
- The elements in the current group is (x, y), (y, N-1-x), (N-1-x, N-1-y), (N-1-y, x), now rotate the these 4 elements, i.e (x, y) <- (y, N-1-x), (y, N-1-x)<- (N-1-x, N-1-y), (N-1-x, N-1-y)<- (N-1-y, x), (N-1-y, x)<- (x, y)
- Print the matrix.
Below is the implementation of the above approach:
C++
// C++ program to rotate a matrix// by 90 degrees#include <bits/stdc++.h>#define N 4using namespace std;// An Inplace function to// rotate a N x N matrix// by 90 degrees in// anti-clockwise directionvoid rotateMatrix(int mat[][N]){ // Consider all squares one by one for (int x = 0; x < N / 2; x++) { // Consider elements in group // of 4 in current square for (int y = x; y < N - x - 1; y++) { // Store current cell in // temp variable int temp = mat[x][y]; // Move values from right to top mat[x][y] = mat[y][N - 1 - x]; // Move values from bottom to right mat[y][N - 1 - x] = mat[N - 1 - x][N - 1 - y]; // Move values from left to bottom mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x]; // Assign temp to left mat[N - 1 - y][x] = temp; } }}// Function to print the matrixvoid displayMatrix(int mat[N][N]){ for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << mat[i][j] << " "; } cout << endl; } cout << endl;}/* Driver code */int main(){ // Test Case 1 int mat[N][N] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // Function call rotateMatrix(mat); // Print rotated matrix displayMatrix(mat); return 0;} |
Java
// Java program to rotate a// matrix by 90 degreesimport java.io.*;class GFG { // An Inplace function to // rotate a N x N matrix // by 90 degrees in // anti-clockwise direction static void rotateMatrix(int N, int mat[][]) { // Consider all squares one by one for (int x = 0; x < N / 2; x++) { // Consider elements in group // of 4 in current square for (int y = x; y < N - x - 1; y++) { // Store current cell in // temp variable int temp = mat[x][y]; // Move values from right to top mat[x][y] = mat[y][N - 1 - x]; // Move values from bottom to right mat[y][N - 1 - x] = mat[N - 1 - x][N - 1 - y]; // Move values from left to bottom mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x]; // Assign temp to left mat[N - 1 - y][x] = temp; } } } // Function to print the matrix static void displayMatrix(int N, int mat[][]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) System.out.print(" " + mat[i][j]); System.out.print("\n"); } System.out.print("\n"); } /* Driver code*/ public static void main(String[] args) { int N = 4; int mat[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // Function call rotateMatrix(N, mat); // Print rotated matrix displayMatrix(N, mat); }}// This code is contributed by Prakriti Gupta |
Python3
# Python3 program to rotate a matrix by 90 degreesN = 4# An Inplace function to rotate# N x N matrix by 90 degrees in# anti-clockwise directiondef rotateMatrix(mat): # Consider all squares one by one for x in range(0, int(N / 2)): # Consider elements in group # of 4 in current square for y in range(x, N-x-1): # store current cell in temp variable temp = mat[x][y] # move values from right to top mat[x][y] = mat[y][N-1-x] # move values from bottom to right mat[y][N-1-x] = mat[N-1-x][N-1-y] # move values from left to bottom mat[N-1-x][N-1-y] = mat[N-1-y][x] # assign temp to left mat[N-1-y][x] = temp# Function to print the matrixdef displayMatrix(mat): for i in range(0, N): for j in range(0, N): print(mat[i][j], end=' ') print("")# Driver Codeif __name__ == "__main__": mat = [[0 for x in range(N)] for y in range(N)] mat = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] # Function call rotateMatrix(mat) # Print rotated matrix displayMatrix(mat)# This code is contributed by saloni1297 |
C#
// C# program to rotate a// matrix by 90 degreesusing System;class GFG { // An Inplace function to // rotate a N x N matrix // by 90 degrees in anti- // clockwise direction static void rotateMatrix(int N, int[, ] mat) { // Consider all // squares one by one for (int x = 0; x < N / 2; x++) { // Consider elements // in group of 4 in // current square for (int y = x; y < N - x - 1; y++) { // store current cell // in temp variable int temp = mat[x, y]; // move values from // right to top mat[x, y] = mat[y, N - 1 - x]; // move values from // bottom to right mat[y, N - 1 - x] = mat[N - 1 - x, N - 1 - y]; // move values from // left to bottom mat[N - 1 - x, N - 1 - y] = mat[N - 1 - y, x]; // assign temp to left mat[N - 1 - y, x] = temp; } } } // Function to print the matrix static void displayMatrix(int N, int[, ] mat) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) Console.Write(" " + mat[i, j]); Console.WriteLine(); } Console.WriteLine(); } // Driver Code static public void Main() { int N = 4; int[, ] mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // Function call rotateMatrix(N, mat); // Print rotated matrix displayMatrix(N, mat); }}// This code is contributed by ajit |
PHP
<?php // PHP program to rotate a // matrix by 90 degrees$N = 4;// An Inplace function to // rotate a N x N matrix// by 90 degrees in // anti-clockwise directionfunction rotateMatrix(&$mat){ global $N; // Consider all // squares one by one for ($x = 0; $x < $N / 2; $x++) { // Consider elements // in group of 4 in // current square for ($y = $x; $y < $N - $x - 1; $y++) { // store current cell // in temp variable $temp = $mat[$x][$y]; // move values from // right to top $mat[$x][$y] = $mat[$y][$N - 1 - $x]; // move values from // bottom to right $mat[$y][$N - 1 - $x] = $mat[$N - 1 - $x][$N - 1 - $y]; // move values from // left to bottom $mat[$N - 1 - $x][$N - 1 - $y] = $mat[$N - 1 - $y][$x]; // assign temp to left $mat[$N - 1 - $y][$x] = $temp; } }}// Function to // print the matrixfunction displayMatrix(&$mat){ global $N; for ($i = 0; $i < $N; $i++) { for ($j = 0; $j < $N; $j++) echo $mat[$i][$j] . " "; echo "\n"; } echo "\n";}// Driver code$mat = array(array(1, 2, 3, 4), array(5, 6, 7, 8), array(9, 10, 11, 12), array(13, 14, 15, 16));// Function callrotateMatrix($mat);// Print rotated matrixdisplayMatrix($mat);// This code is contributed // by ChitraNayal?> |
Javascript
<script>// Javascript program to rotate a// matrix by 90 degrees // An Inplace function to // rotate a N x N matrix // by 90 degrees in // anti-clockwise direction function rotateMatrix(N,mat) { // Consider all squares one by one for (let x = 0; x < N / 2; x++) { // Consider elements in group // of 4 in current square for (let y = x; y < N - x - 1; y++) { // Store current cell in // temp variable let temp = mat[x][y]; // Move values from right to top mat[x][y] = mat[y][N - 1 - x]; // Move values from bottom to right mat[y][N - 1 - x] = mat[N - 1 - x][N - 1 - y]; // Move values from left to bottom mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x]; // Assign temp to left mat[N - 1 - y][x] = temp; } } } // Function to print the matrix function displayMatrix(N,mat) { for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) document.write( " " + mat[i][j]); document.write("<br>"); } document.write("<br>"); } /* Driver program to test above functions */ let N = 4; let mat=[[1, 2, 3, 4],[ 5, 6, 7, 8 ],[9, 10, 11, 12 ],[13, 14, 15, 16]]; // displayMatrix(mat); rotateMatrix(N, mat); // Print rotated matrix displayMatrix(N, mat); // This code is contributed by rag2127. </script> |
Output
4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13
Time Complexity: O(N2), where n is the side of the array. A single traversal of the matrix is needed.
Auxiliary Space: O(1). As a constant space is needed
Example no 2 – Inplace rotate square matrix by 90 degrees by transposing and reversing the matrix:
Follow the given steps to solve the problem:
- Reverse every individual row of the matrix
- Perform Transpose of the matrix
Below is the implementation of the above approach:
C++
// C++ program to rotate a matrix// by 90 degrees#include <bits/stdc++.h>using namespace std;#define N 4// An Inplace function to// rotate a N x N matrix// by 90 degrees in// anti-clockwise directionvoid rotateMatrix(int mat[][N]){ // REVERSE every row for (int i = 0; i < N; i++) reverse(mat[i], mat[i] + N); // Performing Transpose for (int i = 0; i < N; i++) { for (int j = i; j < N; j++) swap(mat[i][j], mat[j][i]); }}// Function to print the matrixvoid displayMatrix(int mat[N][N]){ for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << mat[i][j] << " "; } cout << endl; } cout << endl;}/* Driver code */int main(){ int mat[N][N] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // Function call rotateMatrix(mat); // Print rotated matrix displayMatrix(mat); return 0;} |
Java
// Java program to rotate a// matrix by 90 degreesimport java.io.*;class GFG { // Function to reverse // the given 2D arr[][] static void Reverse(int i, int mat[][], int N) { // Initialise start and end index int start = 0; int end = N - 1; // Till start < end, swap the element // at start and end index while (start < end) { // Swap the element int temp = mat[i][start]; mat[i][start] = mat[i][end]; mat[i][end] = temp; // Increment start and decrement // end for next pair of swapping start++; end--; } } // An Inplace function to // rotate a N x N matrix // by 90 degrees in // anti-clockwise direction static void rotateMatrix(int N, int mat[][]) { // REVERSE every row for (int i = 0; i < N; i++) Reverse(i, mat, N); // Performing Transpose for (int i = 0; i < N; i++) { for (int j = i; j < N; j++) { int temp = mat[i][j]; mat[i][j] = mat[j][i]; mat[j][i] = temp; } } } // Function to print the matrix static void displayMatrix(int N, int mat[][]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) System.out.print(" " + mat[i][j]); System.out.print("\n"); } System.out.print("\n"); } /* Driver code*/ public static void main(String[] args) { int N = 4; int mat[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // Function call rotateMatrix(N, mat); // Print rotated matrix displayMatrix(N, mat); }}// This code is contributed by Aarti_Rathi |
Python3
# Python program to rotate# a matrix by 90 degreesdef rotateMatrix(mat): # reversing the matrix for i in range(len(mat)): mat[i].reverse() # make transpose of the matrix for i in range(len(mat)): for j in range(i, len(mat)): # swapping mat[i][j] and mat[j][i] mat[i][j], mat[j][i] = mat[j][i], mat[i][j]# Function to print the matrixdef displayMatrix(mat): for i in range(0, len(mat)): for j in range(0, len(mat)): print(mat[i][j], end=' ') print()# Driver codeif __name__ == "__main__": mat = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] # Function call rotateMatrix(mat) # Print rotated matrix displayMatrix(mat)# This code is contributed by shivambhagat02(CC). |
C#
// C# program to rotate a// matrix by 90 degreesusing System;class GFG { // Reverse each row of matrix static void reverse(int N, int[, ] mat) { // Traverse each row of [,]mat for (int i = 0; i < N; i++) { // Initialise start and end index int start = 0; int end = N - 1; // Till start < end, swap the element // at start and end index while (start < end) { // Swap the element int temp = mat[i, start]; mat[i, start] = mat[i, end]; mat[i, end] = temp; // Increment start and decrement // end for next pair of swapping start++; end--; } } } // An Inplace function to // rotate a N x N matrix // by 90 degrees in anti- // clockwise direction static void rotateMatrix(int N, int[, ] mat) { reverse(N, mat); // Performing Transpose for (int i = 0; i < N; i++) { for (int j = i; j < N; j++) { int temp = mat[i, j]; mat[i, j] = mat[j, i]; mat[j, i] = temp; } } } // Function to print the matrix static void displayMatrix(int N, int[, ] mat) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) Console.Write(mat[i, j] + " "); Console.Write("\n"); } } // Driver Code static public void Main() { int N = 4; int[, ] mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; // Function call rotateMatrix(N, mat); // Print rotated matrix displayMatrix(N, mat); }}// This code is contributed by Aarti_Rathi |
Javascript
<script>// JavaScript program to rotate// a matrix by 90 degreesfunction rotateMatrix(mat){ // reversing the matrix for(let i = 0; i < mat.length; i++){ mat[i].reverse() } // make transpose of the matrix for(let i = 0; i < mat.length; i++){ for(let j = i; j < mat.length; j++){ // swapping mat[i][j] and mat[j][i] let temp = mat[i][j] mat[i][j] = mat[j][i] mat[j][i] = temp } }}// Function to print the matrixfunction displayMatrix(mat){ for(let i = 0; i < mat.length; i++){ for(let j = 0; j < mat.length; j++){ document.write(mat[i][j],' ') } document.write("</br>") }}let mat = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]rotateMatrix(mat)// Print rotated matrixdisplayMatrix(mat)// This code is contributed by shinjanpatra</script> |
Output
4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13
Time Complexity: O(N2) + O(N2) where N is the size of the array.
Auxiliary Space: O(1). As a constant space is needed
Example no 3 – Implementation by using Vectors in c++
Input - Matrix 1 2 3 4 5 6 7 8 9
Algorithmic steps for implementation –
the algorithmic steps to in-place rotate a square matrix by 90 degrees:
- Transpose the matrix: For each element matrix[i][j] where i < j, swap it with the element matrix[j][i].
- Reverse each row of the matrix: For each row i of the matrix, reverse the order of the elements by swapping matrix[i][j] with matrix[i][n – j – 1] where n is the number of columns in the matrix.
- The matrix is now rotated by 90 degrees in place.
Note: The first step transforms the matrix into its transposed form, and the second step reverses the elements in each row, resulting in a rotation of the matrix by 90 degrees.
Program –
C++
#include <iostream>#include <vector>using namespace std;void rotateMatrix(vector<vector<int>> &matrix) { int n = matrix.size(); // transpose the matrix for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { swap(matrix[i][j], matrix[j][i]); } } // reverse each column for (int i = 0; i < n; i++) { for (int j = 0; j < n / 2; j++) { swap(matrix[j][i], matrix[n - j - 1][i]); } }}int main() { vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; rotateMatrix(matrix); for (int i = 0; i < matrix.size(); i++) { for (int j = 0; j < matrix[0].size(); j++) { cout << matrix[i][j] << " "; } cout << endl; } return 0;} |
Java
public class RotateMatrix { public static void rotateMatrix(int[][] matrix) { int n = matrix.length; // transpose the matrix for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { swap(matrix, i, j, j, i); } } // reverse each column for (int i = 0; i < n; i++) { for (int j = 0; j < n / 2; j++) { swap(matrix, j, i, n - j - 1, i); } } } private static void swap(int[][] matrix, int i, int j, int k, int l) { int temp = matrix[i][j]; matrix[i][j] = matrix[k][l]; matrix[k][l] = temp; } // driver program public static void main(String[] args) { int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; rotateMatrix(matrix); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { System.out.print(matrix[i][j] + " "); } System.out.println(); } }} |
Python3
# Python program for the above approachdef rotateMatrix(matrix): n = len(matrix) # transpose the matrix for i in range(n): for j in range(i,n): temp = matrix[i][j] matrix[i][j] = matrix[j][i] matrix[j][i] = temp # reverse each column for i in range(n): for j in range (int(n/2)): temp = matrix[n-j-1][i] matrix[n-j-1][i] = matrix[j][i] matrix[j][i] = temp # driver programmatrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]rotateMatrix(matrix)for i in range(len(matrix)): for j in range(len(matrix[0])): print(matrix[i][j], end=" ") print("") # THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL23121999) |
C#
using System;using System.Collections.Generic;class Gfg{ static void RotateMatrix(List<List<int>> matrix) { int n = matrix.Count; // Transpose the matrix for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // Reverse each column for (int i = 0; i < n; i++) { for (int j = 0; j < n / 2; j++) { int temp = matrix[j][i]; matrix[j][i] = matrix[n - j - 1][i]; matrix[n - j - 1][i] = temp; } } } static void Main(string[] args) { List<List<int>> matrix = new List<List<int>> { new List<int> { 1, 2, 3 }, new List<int> { 4, 5, 6 }, new List<int> { 7, 8, 9 } }; RotateMatrix(matrix); for (int i = 0; i < matrix.Count; i++) { for (int j = 0; j < matrix[0].Count; j++) { Console.Write(matrix[i][j] + " "); } Console.WriteLine(); } Console.ReadLine(); }} |
Javascript
// JavaScript program for the above approachfunction rotateMatrix(matrix){ let n = matrix.length; // transpose the matrix for(let i = 0; i<n; i++){ for(let j = i; j<n; j++){ let temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // reverse each column for(let i = 0; i<n; i++){ for(let j = 0; j<n/2; j++){ temp = matrix[n - j - 1][i]; matrix[n - j - 1][i] = matrix[j][i]; matrix[j][i] = temp; } }}// driver programlet matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];rotateMatrix(matrix);for(let i = 0; i<matrix.length; i++){ for(let j = 0; j<matrix[0].length; j++){ console.log(matrix[i][j] + " "); } console.log("<br>");}// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGAWRAL2852002) |
Output
3 6 9 2 5 8 1 4 7
Explanation –
- In this implementation, the rotateMatrix function takes a 2D vector matrix as input and rotates the matrix by 90 degrees in the anticlockwise direction in place.
The first step is to transpose the matrix, which is done by swapping the elements matrix[i][j] and matrix[j][i] for i < j.
The second step is to reverse each column of the matrix, which is done by swapping the elements matrix[j][i] and matrix[n – j – 1][i] where n is the number of rows in the matrix. - The time complexity of this algorithm is O(n^2), where n is the number of rows (and columns) in the matrix. This is because the algorithm performs a constant amount of work for each element in the matrix.
- The Auxiliary Space needed for this algorithm is O(1), since no extra space is used.
Exercise: Turn the 2D matrix by 90 degrees in a clockwise direction without using extra space.
Rotate a matrix by 90 degrees without using any extra space | Set 2
This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
