Horje
Rotate a matrix clockwise by 90 degree without using any extra space | Set 3

Given a rectangular matrix mat[][] with N rows and M columns, the task is to rotate the matrix by 90 degrees in a clockwise direction without using extra space.

Examples:

Input: mat[][] = {{1, 2, 3},  {4, 5, 6},   {7, 8, 9},  {10, 11, 12}}
Output: 10 7 4 1 
               11 8 5 2 
               12 9 6 3

Input: mat[][] = {{1, 2, 3, 4, 5, 6}, {7, 8, 9, 10, 11, 12}}
Output: 7 1 
              8 2 
              9 3 
             10 4 
             11 5 
             12 6

 

Note: The approach to rotate square matrix is already discussed as follows: 
 

Approach: The main idea is to perform an in-place rotation.

Follow the below steps to solve the given problem:

  1. Swap all the elements of the sub-matrix min(N, M) * min(N, M), along the main diagonal i.e from the upper top corner to the bottom right corner.
  2. If N is greater than M,
    • Push all the unswapped elements of each column i where (min(N, M) ≤ i) to the ith row.
    • Otherwise, push all the unswapped elements of each row i where (min(N, M) ≤ i) to the ith column.
  3. Reverse each row of the matrix
  4. Print the updated matrix of dimension M × N.

Procedure:

Let the given matrix be : 
1 2 3 
4 5 6 
7 8 9 
10 11 12
13 14 15
Swap all the elements of the sub-matrix min(N, M) * min(N, M) i.e 3 * 3 for this example
1 4 7
2 5 8
3 6 9
10 11 12
13 14 15

Since N > M, push all the unswapped elements of each column i (min(N, M) ≤ i) to the ith row
1 4 7 10 13
2 5 8 11 14
3 6 9 12 15

Reverse each column to get the final rotated matrix as:
13 10 7 4 1
14 11 8 5 2
15 12 9 6 3

Below is the implementation of the above approach:

C++

// C++ program for
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the matrix mat
// with N rows and M columns
void print(vector<vector<int> > mat,
           int N, int M)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << mat[i][j] << " ";
        }
 
        cout << "\n";
    }
}
 
// Function to rotate the matrix
// by 90 degree clockwise
void rotate(vector<vector<int> > mat)
{
    // Number of rows
    int N = mat.size();
 
    // Number of columns
    int M = mat[0].size();
 
    // Swap all the elements along main diagonal
    // in the submatrix min(N, M) * min(N, M)
    for (int i = 0; i < min(N, M); i++) {
        for (int j = i; j < min(N, M); j++) {
 
            // Swap mat[i][j] and mat[j][i]
            swap(mat[i][j], mat[j][i]);
        }
    }
 
    // If N is greater than M
    if (N > M) {
 
        // Push all the unswapped elements
        // of ith column to ith row
        for (int i = 0; i < M; i++) {
            for (int j = min(N, M); j < N; j++) {
                mat[i].push_back(mat[j][i]);
            }
        }
    }
    else {
        // Resize mat to have M rows
        mat.resize(M, {});
 
        // Push all the unswapped elements
        // of ith column to ith row
        for (int i = min(N, M); i < M; i++) {
            for (int j = 0; j < N; j++) {
                mat[i].push_back(mat[j][i]);
            }
        }
    }
 
    // Reverse each row of the matrix
    for (int i = 0; i < M; i++) {
        reverse(mat[i].begin(), mat[i].end());
    }
 
    // Print the final matrix
    print(mat, M, N);
}
 
// Driver Code
int main()
{
    // Input
    vector<vector<int> > mat = { { 1, 2, 3 },
                                 { 4, 5, 6 },
                                 { 7, 8, 9 },
                                 { 10, 11, 12 } };
 
    // Function Call
    rotate(mat);
 
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
 
class GFG {
  // Java program for
  // the above approach
 
  // Function to print the matrix mat
  // with N rows and M columns
  static void print(ArrayList<ArrayList<Integer>> mat,int N, int M)
  {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        System.out.print(mat.get(i).get(j) + " ");
      }
 
      System.out.println();
    }
  }
 
  // Function to rotate the matrix
  // by 90 degree clockwise
  static void rotate(ArrayList<ArrayList<Integer>> mat)
  {
    // Number of rows
    int N = mat.size();
 
    // Number of columns
    int M = mat.get(0).size();
 
    // Swap all the elements along main diagonal
    // in the submatrix min(N, M) * min(N, M)
    for (int i = 0; i < Math.min(N, M); i++) {
      for (int j = i; j < Math.min(N, M); j++) {
 
        // Swap mat[i][j] and mat[j][i]
        int temp = mat.get(i).get(j);
        mat.get(i).set(j,mat.get(j).get(i));
        mat.get(j).set(i,temp);
      }
    }
 
    // If N is greater than M
    if (N > M) {
 
      // Push all the unswapped elements
      // of ith column to ith row
      for (int i = 0; i < M; i++) {
        for (int j = Math.min(N, M); j < N; j++) {
          mat.get(i).add(mat.get(j).get(i));
        }
      }
    }
    else {
      // Resize mat to have M rows
      mat = new ArrayList<>(M);
      for(int i=0;i<M;i++){
        mat.add(i , new ArrayList<>());
      }
 
      // Push all the unswapped elements
      // of ith column to ith row
      for (int i = Math.min(N, M); i < M; i++) {
        for (int j = 0; j < N; j++) {
          mat.get(i).add(mat.get(j).get(i));
        }
      }
    }
 
    // Reverse each row of the matrix
    for (int i = 0; i < M; i++) {
      Collections.reverse(mat.get(i));
    }
 
    // Print the final matrix
    print(mat, M, N);
  }
 
  /* Driver program to test above function*/
  public static void main(String args[])
  {
    // Input
    ArrayList<ArrayList<Integer>> mat = new ArrayList<>();
    mat.add(new ArrayList<Integer>(Arrays.asList(1,2,3)));
    mat.add(new ArrayList<Integer>(Arrays.asList(4,5,6)));
    mat.add(new ArrayList<Integer>(Arrays.asList(7,8,9)));
    mat.add(new ArrayList<Integer>(Arrays.asList(10,11,12)));
 
    // Function Call
    rotate(mat);
  }
}
 
// This code is contributed by shinjanpatra

Python3

# Python3 program for
# the above approach
 
# Function to print the matrix mat
# with N rows and M columns
def Print(mat, N, M):
 
    for i in range(N):
        for j in range(M):
            print(mat[i][j] , end = " ")
        print()
 
# Function to rotate the matrix
# by 90 degree clockwise
def rotate(mat):
 
    # Number of rows
    N = len(mat)
 
    # Number of columns
    M = len(mat[0])
 
    # Swap all the elements along main diagonal
    # in the submatrix min(N, M) * min(N, M)
    for i in range(min(N, M)):
        for j in range(i,min(N, M)):
 
            # Swap mat[i][j] and mat[j][i]
            mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
 
    # If N is greater than M
    if (N > M):
 
        # Push all the unswapped elements
        # of ith column to ith row
        for i in range(M):
            for j in range(min(N, M),N):
                mat[i].append(mat[j][i])
             
    else:
        # Resize mat to have M rows
        mat = [[] for i in range(M)]
 
        # Push all the unswapped elements
        # of ith column to ith row
        for i in range(min(N, M),M):
            for j in range(N):
                mat[i].append(mat[j][i])
 
    # Reverse each row of the matrix
    for i in range(M):
        mat[i] = mat[i][::-1]
 
    # Print the final matrix
    Print(mat, M, N)
 
# Driver Code
 
# Input
mat = [ [ 1, 2, 3 ],
        [ 4, 5, 6 ],
        [ 7, 8, 9 ],
        [ 10, 11, 12 ] ]
 
# Function Call
rotate(mat)
 
# This code is contributed by shinjanpatra

C#

/*package whatever //do not write package name here */
using System;
using System.Collections.Generic;
 
class GFG
{
  // Java program for
  // the above approach
 
  // Function to print the matrix mat
  // with N rows and M columns
  static void print(List<List<int>> mat,int N, int M)
  {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        Console.Write(mat[i][j] + " ");
      }
 
      Console.WriteLine();
    }
  }
 
  // Function to rotate the matrix
  // by 90 degree clockwise
  static void rotate(List<List<int>> mat)
  {
    // Number of rows
    int N = mat.Count;
 
    // Number of columns
    int M = mat[0].Count;
 
    // Swap all the elements along main diagonal
    // in the submatrix Min(N, M) * Min(N, M)
    for (int i = 0; i < Math.Min(N, M); i++) {
      for (int j = i; j < Math.Min(N, M); j++) {
 
        // Swap mat[i][j] and mat[j][i]
        int temp = mat[i][j];
        mat[i][j] =mat[j][i];
        mat[j][i] = temp;
      }
    }
 
    // If N is greater than M
    if (N > M) {
 
      // Push all the unswapped elements
      // of ith column to ith row
      for (int i = 0; i < M; i++) {
        for (int j = Math.Min(N, M); j < N; j++) {
          mat[i].Add(mat[j][i]);
        }
      }
    }
    else {
      // Resize mat to have M rows
      mat = new List<List<int>>(M);
      for(int i=0;i<M;i++){
        mat[i] =  new List<int>();
      }
 
      // Push all the unswapped elements
      // of ith column to ith row
      for (int i = Math.Min(N, M); i < M; i++) {
        for (int j = 0; j < N; j++) {
          mat[i].Add(mat[j][i]);
        }
      }
    }
 
    // Reverse each row of the matrix
    for (int i = 0; i < M; i++) {
      mat[i].Reverse();
    }
 
    // Print the final matrix
    print(mat, M, N);
  }
 
  /* Driver program to test above function*/
  public static void Main()
  {
    // Input
    List<List<int>> mat =   new List<List<int>>();
    mat.Add(new List<int>(new int[] {1, 2, 3}));
    mat.Add(new List<int>(new int[] {4, 5, 6}));
    mat.Add(new List<int>(new int[] {7, 8, 9}));
    mat.Add(new List<int>(new int[] {10, 11, 12}));
 
    // Function Call
    rotate(mat);
  }
}
 
// This code is contributed by Saurabh Jaiswal

Javascript

<script>
 
// JavaScript program for
// the above approach
 
// Function to print the matrix mat
// with N rows and M columns
function print(mat,N,M)
{
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            document.write(mat[i][j] , " ");
        }
 
        document.write("</br>");
    }
}
 
// Function to rotate the matrix
// by 90 degree clockwise
function rotate(mat)
{
    // Number of rows
    let N = mat.length;
 
    // Number of columns
    let M = mat[0].length;
 
    // Swap all the elements along main diagonal
    // in the submatrix min(N, M) * min(N, M)
    for (let i = 0; i < Math.min(N, M); i++) {
        for (let j = i; j < Math.min(N, M); j++) {
 
            // Swap mat[i][j] and mat[j][i]
            let temp = mat[i][j];
            mat[i][j] = mat[j][i];
            mat[j][i] = temp;
        }
    }
 
    // If N is greater than M
    if (N > M) {
 
        // Push all the unswapped elements
        // of ith column to ith row
        for (let i = 0; i < M; i++) {
            for (let j = Math.min(N, M); j < N; j++) {
                mat[i].push(mat[j][i]);
            }
        }
    }
    else {
        // Resize mat to have M rows
        mat = new Array(M).fill(0).map(()=>[])
 
        // Push all the unswapped elements
        // of ith column to ith row
        for (let i = Math.min(N, M); i < M; i++) {
            for (let j = 0; j < N; j++) {
                mat[i].push(mat[j][i]);
            }
        }
    }
 
    // Reverse each row of the matrix
    for (let i = 0; i < M; i++) {
        mat[i] = mat[i].reverse();
    }
 
    // Print the final matrix
    print(mat, M, N);
}
 
// Driver Code
 
// Input
let mat = [ [ 1, 2, 3 ],
        [ 4, 5, 6 ],
        [ 7, 8, 9 ],
        [ 10, 11, 12 ] ];
 
// Function Call
rotate(mat);
 
// This code is contributed by shinjanpatra
 
</script>

Output

10 7 4 1 
11 8 5 2 
12 9 6 3

Time Complexity: O(N * M)
Auxiliary Space: O(1)

 


 


Reffered: https://www.geeksforgeeks.org

Matrix

Related
Maximize product of a matrix by repeatedly multiplying pairs of adjacent cells with -1 Maximize product of a matrix by repeatedly multiplying pairs of adjacent cells with -1
Print the indices for every row of a grid from which escaping from the grid is possible Print the indices for every row of a grid from which escaping from the grid is possible
Find the person who will finish last Find the person who will finish last
Rotate all Matrix elements except the diagonal K times by 90 degrees in clockwise direction Rotate all Matrix elements except the diagonal K times by 90 degrees in clockwise direction
Generate matrix from given Sparse Matrix using Linked List and reconstruct the Sparse Matrix Generate matrix from given Sparse Matrix using Linked List and reconstruct the Sparse Matrix

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje