Tutorialspoint.dev

Rotate a matrix by 90 degree without using any extra space | Set 2

Given a square matrix, turn it by 90 degrees in anti-clockwise direction without using any extra space.

Examples:

Input
 1  2  3
 4  5  6
 7  8  9
Output:
 3  6  9 
 2  5  8 
 1  4  7 

Input:
 1  2  3  4 
 5  6  7  8 
 9 10 11 12 
13 14 15 16 
Output:
 4  8 12 16 
 3  7 11 15 
 2  6 10 14 
 1  5  9 13


An approach that requires extra space is already discussed in below set:
Inplace rotate square matrix by 90 degrees | Set 1

In this post another approach is discussed which is much simpler than the above approach.

There are two steps :

  1. Find transpose of matrix.
  2. Reverse columns of the transpose.

Illustration of above steps :

Let the given matrix be
1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

First we find transpose.
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

Then we reverse elements of every column.
4 8 12 16
3 7 11 15
2 6 10 14
1 5  9 13

Below is the implementation of above steps.

C++

// C++ program for left rotation of matrix by 90
// degree without using extra space
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4
  
// After transpose we swap elements of column
// one by one for finding left rotation of matrix
// by 90 degree
void reverseColumns(int arr[R][C])
{
    for (int i = 0; i < C; i++)
        for (int j = 0, k = C - 1; j < k; j++, k--)
            swap(arr[j][i], arr[k][i]);
}
  
// Function for do transpose of matrix
void transpose(int arr[R][C])
{
    for (int i = 0; i < R; i++)
        for (int j = i; j < C; j++)
            swap(arr[i][j], arr[j][i]);
}
  
// Function for print matrix
void printMatrix(int arr[R][C])
{
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++)
            cout << arr[i][j] << " ";
        cout << ' ';
    }
}
  
// Function to anticlockwise rotate matrix
// by 90 degree
void rotate90(int arr[R][C])
{
    transpose(arr);
    reverseColumns(arr);
}
  
// Driven code
int main()
{
    int arr[R][C] = { { 1, 2, 3, 4 },
                      { 5, 6, 7, 8 },
                      { 9, 10, 11, 12 },
                      { 13, 14, 15, 16 } };
    rotate90(arr);
    printMatrix(arr);
    return 0;
}

Java

// JAVA Code for left Rotation of a
// matrix by 90 degree without using
// any extra space
import java.util.*;
  
class GFG {
  
    // After transpose we swap elements of
    // column one by one for finding left
    // rotation of matrix by 90 degree
    static void reverseColumns(int arr[][])
    {
        for (int i = 0; i < arr[0].length; i++)
            for (int j = 0, k = arr[0].length - 1;
                 j < k; j++, k--) {
                int temp = arr[j][i];
                arr[j][i] = arr[k][i];
                arr[k][i] = temp;
            }
    }
  
    // Function for do transpose of matrix
    static void transpose(int arr[][])
    {
        for (int i = 0; i < arr.length; i++)
            for (int j = i; j < arr[0].length; j++) {
                int temp = arr[j][i];
                arr[j][i] = arr[i][j];
                arr[i][j] = temp;
            }
    }
  
    // Function for print matrix
    static void printMatrix(int arr[][])
    {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++)
                System.out.print(arr[i][j] + " ");
            System.out.println("");
        }
    }
  
    // Function to anticlockwise rotate
    // matrix by 90 degree
    static void rotate90(int arr[][])
    {
        transpose(arr);
        reverseColumns(arr);
    }
  
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr[][] = { { 1, 2, 3, 4 },
                        { 5, 6, 7, 8 },
                        { 9, 10, 11, 12 },
                        { 13, 14, 15, 16 } };
  
        rotate90(arr);
        printMatrix(arr);
    }
}
  
// This code is contributed by Arnav Kr. Mandal.

C#

// C# program for left rotation
// of matrix by 90 degree
// without using extra space
using System;
  
class GFG {
    static int R = 4;
    static int C = 4;
  
    // After transpose we swap
    // elements of column one
    // by one for finding left
    // rotation of matrix by
    // 90 degree
    static void reverseColumns(int[, ] arr)
    {
        for (int i = 0; i < C; i++)
            for (int j = 0, k = C - 1;
                 j < k; j++, k--) {
                int temp = arr[j, i];
                arr[j, i] = arr[k, i];
                arr[k, i] = temp;
            }
    }
  
    // Function for do
    // transpose of matrix
    static void transpose(int[, ] arr)
    {
        for (int i = 0; i < R; i++)
            for (int j = i; j < C; j++) {
                int temp = arr[j, i];
                arr[j, i] = arr[i, j];
                arr[i, j] = temp;
            }
    }
  
    // Function for print matrix
    static void printMatrix(int[, ] arr)
    {
  
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++)
                Console.Write(arr[i, j] + " ");
            Console.WriteLine("");
        }
    }
  
    // Function to anticlockwise
    // rotate matrix by 90 degree
    static void rotate90(int[, ] arr)
    {
        transpose(arr);
        reverseColumns(arr);
    }
  
    // Driver code
    static void Main()
    {
        int[, ] arr = { { 1, 2, 3, 4 },
                        { 5, 6, 7, 8 },
                        { 9, 10, 11, 12 },
                        { 13, 14, 15, 16 } };
  
        rotate90(arr);
        printMatrix(arr);
    }
  
    // This code is contributed
    // by Sam007
}

Python 3

# Python 3 program for left rotation of matrix by 90
# degree without using extra space
  
R = 4
C = 4
   
# After transpose we swap elements of column
# one by one for finding left rotation of matrix
# by 90 degree
def reverseColumns(arr):
    for i in range(C):
        j = 0
        k = C-1
        while j < k:
            t = arr[j][i]
            arr[j][i] = arr[k][i]
            arr[k][i] = t
            j += 1
            k -= 1
    
# Function for do transpose of matrix
def transpose(arr):
    for i in range(R):
        for j in range(i, C):
            t = arr[i][j]
            arr[i][j] = arr[j][i]
            arr[j][i] = t
   
# Function for print matrix
def printMatrix(arr):
    for i in range(R):
        for j in range(C):
            print(str(arr[i][j]), end =" ")
        print()
   
# Function to anticlockwise rotate matrix
# by 90 degree
def rotate90(arr):
    transpose(arr)
    reverseColumns(arr)
   
# Driven code
arr = [[1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
        [13, 14, 15, 16]
    ];
rotate90(arr)
printMatrix(arr)

PHP

<?php
// PHP program for left rotation of matrix by 90
  
$R = 4;
$C = 4;
// Function to rotate the matrix by 90 degree
function reverseColumns(&$arr)
{
    global $C;
    for ($i = 0; $i < $C; $i++)
    {
        for ($j = 0, $k = $C - 1; $j < $k; $j++, $k--)
        {
            $t = $arr[$j][$i];
            $arr[$j][$i] = $arr[$k][$i];
            $arr[$k][$i] = $t;
        }
    }       
}
   
// Function for transpose of matrix
function transpose(&$arr)
{
    global $R, $C;
    for ($i = 0; $i < $R; $i++)
    {
        for ($j = $i; $j < $C; $j++)
        {
            $t = $arr[$i][$j];
            $arr[$i][$j] = $arr[$j][$i];
            $arr[$j][$i] = $t;
        }
    }
}
   
// Function for display the matrix
function printMatrix(&$arr)
{
    global $R, $C;
    for ($i = 0; $i < $R; $i++) {
        for ($j = 0; $j < $C; $j++)
            echo $arr[$i][$j]." ";
        echo " ";
    }
}
   
// Function to anticlockwise rotate matrix
// by 90 degree
function rotate90(&$arr)
{
    transpose($arr);
    reverseColumns($arr);
}
   
// Driven code
  
$arr = array( array( 1, 2, 3, 4 ),
                 array( 5, 6, 7, 8 ),
                 array( 9, 10, 11, 12 ),
                 array( 13, 14, 15, 16 ) );
rotate90($arr);
printMatrix($arr);
return 0;
?>


Output:

4 8 12 16 
3 7 11 15 
2 6 10 14 
1 5 9 13 

Time complexity :O(R*C)
Space complexity :O(1)

The above steps/program do left (or anticlockwise) rotation, how to right (or clockwise) rotate?
To right rotate, we do following steps.

  1. Find transpose of matrix.
  2. Reverse rows of the transpose.

Illustration of above steps :

Let the given matrix be
1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

First we find transpose.
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

Then we reverse elements of every row.
13  9 5 1
14 10 6 2
15 11 7 3 
16 12 8 4

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter