Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example:
2.1.1.
Input
2.1.2.
Output
2.2.
Explanation
3.
Algorithm
4.
Implementation
4.1.
C++ code
4.2.
Java Code
4.3.
Python Code
4.3.1.
Input
4.3.2.
Output
5.
Complexities Analysis
5.1.
Time Complexity
5.2.
Space Complexity
6.
Frequently Asked Questions
6.1.
What are the benefits of Python?
6.2.
What is an interpreted language?
6.3.
What is pass in Python?
6.4.
Explain the usage of self in python class?
6.5.
What is __init__ in Python?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Rotate Matrix Elements

Author Anant Dhakad
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog will look at how to rotate matrix elements clockwise. This problem involves arrays and loops. Array-based questions are the most popular in coding interviews and programming contests. We will take up a coding challenge that requires a better understanding of the problem statement. You need greater observatory skills to identify the trick to solve the problem.

Multi-Dimensional Array

Must Read, Array Implementation of Queue and   Rabin Karp Algorithm

Problem Statement

Given an integer matrix of size N x M, where ‘N’ is the number of rows and ‘M’ is the number of columns, You task is to rotate all matrix elements in the clockwise direction. You will get a better understanding of the problem from the following example.

Example:

Input

1 2 3
4 5 6
7 8 9

Output

4 1 2
7 5 3
8 9 6

Explanation

We need to rotate the matrix NxM in the clockwise direction, where N is the number of rows and M is the number of columns in a matrix.

Start Thinking

Don’t worry we will go through the algorithm once and then all your doubts will be clear. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm

We are going to use loops to solve this problem. We will traverse in a spiral fashion and rotate all rings.

For rotating a single ring, follow these steps:

  1. Rotate the top row of the ring.
     
  2. Rotate the last column (on the right side) of the ring.
     
  3. Rotate the bottom row of the ring.
     
  4. Rotate the first column (on the left side) of the ring.

Implementation

Now let's look at the implementation of the above algorithm in C++, Java, and Python.

C++ code

/* C++ program to rotate matrix elements */
#include <bits/stdc++.h>

# define R 3
# define C 3

using namespace std;

/* function to rotate matrix where m = R and n = C */
void rotatematrix(int m, int n, int mat[R][C]) {
    
    int row = 0;
    int col = 0;
    int prev;
    int curr;

    /* we will store starting row index in "row" while store starting column index in "col" */
    while (row < m && col < n) {
        if (row + 1 == m || col + 1 == n)
            break;

        /* "prev" will store the 1st element of next row */
        prev = mat[row + 1][col];

        /* Move 1st row elements from the remaining rows */
        for (int i = col; i < n; i++) {
            curr = mat[row][i];
            mat[row][i] = prev;
            prev = curr;
        }
        row++;

        /* Move last column elements from the remaining columns */
        for (int i = row; i < m; i++) {
            curr = mat[i][n-1];
            mat[i][n-1] = prev;
            prev = curr;
        }
        n--;

        /* Move last row elements from the remaining rows */
        if (row < m) {
            for (int i = n-1; i >= col; i--) {
                curr = mat[m-1][i];
                mat[m-1][i] = prev;
                prev = curr;
            }
        }
        m--;

        /* Move 1st column elements from the remaining rows */
        if (col < n) {
            for (int i = m-1; i >= row; i--) {
                curr = mat[i][col];
                mat[i][col] = prev;
                prev = curr;
            }
        }
        col++;
    }

    /* print the rotated matrix */
    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++)
            cout << mat[i][j] << " ";
        cout << endl;
    }
}

/* Main function */
int main() {
    
    /* Test case on which we are going to check our code */
    int a[R][C] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
  
    /* function to rotate matrix and print the rotated matrix */
    rotatematrix(R, C, a);
  
    return 0;
}

 

Java Code

/* Java program to rotate matrix elements */
import java.lang.*;
import java.util.*;

class Main {
    
    static int R = 3;
    static int C = 3;

    /* function to rotate matrix where m = R and n = C */
    static void rotatematrix(int m, int n, int mat[][]) {
        
        int row = 0;
        int col = 0;
        int prev;
        int curr;
        
        /* we will store starting row index in "row" while store starting column index in "col" */
        while (row < m && col < n) {
            if (row + 1 == m || col + 1 == n)
                break;
            
            /* "prev" will store the 1st element of next row */
            prev = mat[row + 1][col];
            
            /* Move 1st row elements from the remaining rows */
            for (int i = col; i < n; i++) {
                curr = mat[row][i];
                mat[row][i] = prev;
                prev = curr;
            }
            row++;
            
            /* Move last column elements from the remaining columns */
            for (int i = row; i < m; i++) {
                curr = mat[i][n-1];
                mat[i][n-1] = prev;
                prev = curr;
            }
            n--;
            
            /* Move last row elements from the remaining rows */
            if (row < m) {
                for (int i = n-1; i >= col; i--) {
                    curr = mat[m-1][i];
                    mat[m-1][i] = prev;
                    prev = curr;
                }
            }
            m--;
            
            /* Move 1st column elements from the remaining rows */
            if (col < n) {
                for (int i = m-1; i >= row; i--) {
                    curr = mat[i][col];
                    mat[i][col] = prev;
                    prev = curr;
                }
            }
            col++;
        }
        
        /* print the rotated matrix */
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++)
                System.out.print( mat[i][j] + " ");
            System.out.print("\n");
        }
    }

    /* Main function */
    public static void main(String[] args) {
        
        /* Test case on which we are going to check our code */
        int a[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        
        /* function to rotate matrix and print the rotated matrix */
        rotatematrix(R, C, a);
    }
}

 

Python Code

# Python program to rotate matrix elements

# function to rotate matrix where m = R and n = C
def rotateMatrix(mat):
    
    if not len(mat):
        return
    
    top = 0
    bottom = len(mat)-1
    left = 0
    right = len(mat[0])-1
    
    # we will store starting row index in "top" while store starting column index in "left"
    while left < right and top < bottom:

        # "prev" will store the 1st element of next row
        prev = mat[top+1][left]

        # Move 1st row elements from the remaining rows
        for i in range(left, right+1):
            curr = mat[top][i]
            mat[top][i] = prev
            prev = curr
        top += 1
        
        # Move last column elements from the remaining columns
        for i in range(top, bottom+1):
            curr = mat[i][right]
            mat[i][right] = prev
            prev = curr
        right -= 1

        # Move last row elements from the remaining rows
        for i in range(right, left-1, -1):
            curr = mat[bottom][i]
            mat[bottom][i] = prev
            prev = curr
        bottom -= 1

        # Move elements of leftmost column one step upwards
        for i in range(bottom, top-1, -1):
            curr = mat[i][left]
            mat[i][left] = prev
            prev = curr
        left += 1

    return mat

# print the rotated matrix
def printMatrix(mat):
    for row in mat:
        print(row)


# Test case on which we are going to check our code
matrix =[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

# function to rotate matrix and print the rotated matrix
matrix = rotateMatrix(matrix)

printMatrix(matrix)

Input

1 2 3
4 5 6
7 8 9

Output

4 1 2
7 5 3
8 9 6

Complexities Analysis

Time Complexity

O(m * n), where m represents row count, and n represents column count.

Reason: We are running a nested loop where the first loop contains elements m, and the other loop inside the first loop has elements n.

Space Complexity

O(1)

Reason: We don’t require additional space to store any data.

Check out this problem - Matrix Median

Frequently Asked Questions

What are the benefits of Python?

Python is a high-level, interpreted programming language. Python also has objects, modules, threads, exception handling, and automatic memory management, all of which aid in modeling real-world issues and developing applications to solve them.

What is an interpreted language?

The statements in an Interpreted language are executed line by line. Interpreted languages include Python, Javascript, R, PHP, and Ruby, to name a few. An interpreted language program runs directly from the source code without requiring a compilation phase.

What is pass in Python?

In Python, the pass keyword denotes a null operation. It is commonly used to fill in blank blocks of code that may execute during runtime but have not yet been written. We may encounter issues during code execution without the pass statement.

Explain the usage of self in python class?

Self is used to show the class instance. You can access the class attributes and methods in Python with this keyword. It connects the attributes to the arguments. However, unlike C++, Python does not include a keyword called self.

What is __init__ in Python?

Whenever an object is created, the constructor method __init__ is immediately called to allocate memory. The __init__ method is connected with all classes. It aids in the separation of class methods and properties from local variables.

Conclusion

In this article, we have learned how to rotate the matrix in the clockwise direction. To continue learning more about DSA problems, check out our other blogs on the print matrixtypes of matrix, and operations on matrices.

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Thank You
Previous article
Rotate Each Ring of Matrix Clockwise by K Elements
Next article
Interchange elements of first and last rows in matrix
Live masterclass