Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Test Case
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Solution
4.1.
Algorithm
4.2.
Visualisation
4.3.
Implementation
4.3.1.
C++ Code
4.3.2.
Java Code
4.3.3.
Python Code
4.4.
Output
4.5.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is the time and space complexity of traversing a matrix of size MxN?
5.2.
How many ways can we traverse a matrix?
5.3.
What do you mean by row-major and column-major traversal for a matrix?
5.4.
How to check if the given two matrices are equal?
6.
Conclusion
Last Updated: Mar 27, 2024

Rotate a Matrix Right by K Elements

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

Introduction

Welcome readers! We hope that you are doing great.

Matrices are essential concepts for programmers, as they contribute to building the fundamental concepts of good programmers.

Today, we will discuss the problem Rotate a Matrix Right by K elements with proper explanation, implementation and diagram.

From this blog, you will get an idea about the rotation concept of matrices. After reading this blog, the concept of 2D array rotation will be clear to you. So follow the article till the end.

So, without further ado, let's start our discussion.

Problem Statement

You're given a Matrix of size MxN and an Integer K. You need to rotate the matrix to the right by K elements.

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

Test Case

Below is an example of the test case.

Input

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

2

Output

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

Explanation

Given input Matrix is, 

{

{1,2,3,4},

{5,6,7,8},

{9,10,11,12}

}

and k = 2.

After two rotations to the right of the matrix, the output comes out to be,

{

{3,4,1,2},

{7,8,5,6},

{11,12,9,10}

}

Below is the explanation,

Solution

A simple solution to this problem is simply rotating each row to the right by k elements. If we do so, we will get our final answer. 

If you want to learn about the right rotation of an array in detail, follow these articles on Array Rotation.

Below is the algorithm.

Algorithm

  • Traverse each row of the matrix.
  • Create a temporary array of sizes n (where n = number of columns)
  • Copy the elements of the current row to the temporary array.
  • Replace the current row's first k elements with the temporary array's last k elements.
  • Replace the current row's last n - k elements with the temporary array's first n - k elements.
  • Repeat the above process for all rows in the matrix.

Visualisation

Below is the visualisation of the above algorithm,
 

Implementation

Here, in this section, we will implement the above algorithm in different languages.

C++ Code

#include <bits/stdc++.h>
using namespace std;

#define m 3
#define n 4

int main()
{
    int matrix[m][n] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
    int k = 2;

    // for the case when k > n
    // here k = 2;

    k %= n;

    // traverse each row of the matrix

    for (int i = 0; i < m; i++)
    {

        // for each row

        int arr[n];

        // copy all elements of the current row to the arr

        for (int j = 0; j < n; j++)
        {
            arr[j] = matrix[i][j];
        }

        // replace the first k elements of the current row with the last k elements of the arr

        for (int j = 0; j < k; j++)
        {
            matrix[i][j] = arr[n - k + j];
        }

        // replace last n - k elements of the current row with the first n - k elements of the arr
        for (int j = k; j < n; j++)
        {
            matrix[i][j] = arr[j - k];
        }
    }

    // print the matrix after rotation

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << matrix[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}


Java Code

class Main {
    public static void main(String[] args) {

        int m = 3;
        int n = 4;
        // given k
        int k = 2;
        // given matrix
        int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };

        // for the case when k > n
        // here k = 2;
        k %= n;

        // traverse each row of the matrix

        for (int i = 0; i < m; i++) {

            // for each row

            int[] arr = new int[n];

            // copy all elements of the current row to the arr

            for (int j = 0; j < n; j++) {
                arr[j] = matrix[i][j];
            }

            // replace the first k elements of the current row with the last k elements of the arr

            for (int j = 0; j < k; j++) {
                matrix[i][j] = arr[n - k + j];
            }

            // replace last n - k elements of the current row with the first n - k elements of the arr
            for (int j = k; j < n; j++) {
                matrix[i][j] = arr[j - k];
            }
        }

        // print the matrix after rotation

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }

    }
}


Python Code

# dimension of the matrix
m = 3
n = 4

# given k
k = 2

# given matrix
matrix =  [[1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12]]

# for the case when k > n
# here k = 2;
k %= n

# traverse each row of the matrix
for i in range(0 , m):
    # for each row
    arr = []

    # copy all elements of the current row to arr
    for j in range(0 , n):
        arr.append(matrix[i][j])
   
    # replace the first k elements of the current row with the last k elements of the arr
    for j in range(0 , k):
        matrix[i][j] = arr[n - k + j]
   
    # replace the last n - k elements of the current row with the first n - k elements of the arr
    for j in range(k , n):
        matrix[i][j] = arr[j - k]

# print the matrix after rotation
for i in range(0 , m):
    for j in range(0 , n):
        print(matrix[i][j] , end =" ")
    print()

Output

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

Complexity Analysis

If you want to learn about time and space complexity, follow the Time and Space Complexity article.

Time complexity: O(MN)

Space Complexity: O(N)

Also see,  Rabin Karp Algorithm

Frequently Asked Questions

What is the time and space complexity of traversing a matrix of size MxN?

Time Complexity: O(MN)

Space Complexity: O(1)

 

How many ways can we traverse a matrix?

There are mainly two ways we can traverse a matrix,

  • Row Major Traversal
  • Column Major Traversal
     

What do you mean by row-major and column-major traversal for a matrix?

Row-major traversal: If we traverse a matrix row by row, it is called row-major traversal.

Column-major traversal: When we traverse a matrix column by column, it is called column-major traversal.
 

How to check if the given two matrices are equal?

To check whether two given matrices are equal or not, you can do the followings:

  • Check if they have the same dimensions.
  • Check if all corresponding pairs of elements in the two matrices are equal.

Conclusion

In this article, we have extensively discussed Rotate a Matrix Right by K Elements.

We started with the basic introduction, then we discussed,

  • The Problem Statement
  • A Test Case
  • and Solution

We hope you have got some insight through this article regarding Rotating a Matrix Right by k Elements.

If you want to learn more, follow our articles on Operation On MatricesBook Allocation ProblemHow to Multiply Two Matrices, and  Minimum Sum Path in a Matrix.

Explore our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations and much more.!

Happy Reading!

Previous article
Rotate a Matrix by 180-degree
Next article
Rotate Each Ring of Matrix Clockwise by K Elements
Live masterclass