Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
What is Matrix?
1.2.
Problem statement
1.3.
Sample Examples
2.
Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
Which data structure is used to form Matrix? Explain it.
3.2.
What is the need for a two-dimensional array?
3.3.
How are two-dimensional arrays stored in memory?
3.4.
How can we obtain data from a two-dimensional array?
4.
Conclusion
Last Updated: Mar 27, 2024

Check if all rows of a matrix are circular rotations of each other

Author Rupal Saluja
0 upvote

Introduction

In this blog, we will try to grab hold of a two-dimensional array data structure problem. Through that problem, we will try to understand how to approach any two-dimensional array data structure problem. The examples presented will help you clear your concepts, Pseudocode will provide you with an immediate solution, and the implementation part will give you a detailed understanding of every step.

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

What is Matrix?

A matrix can be made using a two-dimensional array data structure. A multidimensional array is an array within arrays, that is, each element of the multidimensional array is an array itself. Similarly, in a two-dimensional array, every element of an array is an array in itself. 

For Example, to create a multidimensional array presented below, we use the following line of code.

int [][] a= new int [3][4];

This two-dimensional array has the capacity to store up to 12 elements.

Two Dimensional Array

Problem statement

Firstly, we will have a look at what exactly the problem says.

We are given a matrix and we need to check whether all the rows of a matrix are circular rotations of each other or not. Here, we have assumed that no index in the matrix remains empty and all the indices have some value. There are no exceptions in this problem.

Here, we are assuming that the given matrix is a Square Matrix.

Sample Examples

Example 1:

Explanation: In the above example, we have taken a ‘4*4’ integer matrix. Each row will be checked whether it is the circular rotation of the previous one or not. The first row has four elements, the second is rotated once, the third row is the rotation of the second and so on. To understand it a little better, please refer to the image provided below. 

 

Example 2:

Explanation: In the above example, we have taken a char square matrix of ‘4*4’. Each row will be checked whether it is the circular rotation of the previous one or not. The first row has four elements, the second is the rotation of the first. But, when we check the third row, no circular rotation was observed there. Hence, after that, no rows are checked. Even if, there could be a circular rotation afterward, the output still remains ‘No’.

Approach

Step 1

Firstly, we will check whether the input matrix is a row matrix or a column matrix. If that is the case, we will return true.

Step 2

Then, we will start by checking the element present at the upper left diagonal of the matrix. The loop continues until the condition becomes false. In such a situation, we will return false. 

Step 3

After that, we will check if the first element of the current row and the last element of the previous row are equal or not, if they are then we will continue else we will return false.

Step 4

The comparison continues until the condition becomes false. 

Step 5

If true is returned, then the output will be, ‘Yes.’

If false is returned, then the output will be, ‘ No.’

Pseudocode

bool check_circular_rotation(vector<vector<int>> a)
{
    int n = a.size(), m = a[0].size();
    // if there is only one row or one column in matrix then return true
    if (n == 1 || m == 1)
        return true;
        
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            // checking for element present at upper left diagonal of matrix
            if (a[i][j] != a[i - 1][j - 1])
                return false;
        }
        // checking for first element of current row and last element of previous row
        if (a[i][0] != a[i - 1][m - 1])
        {
            return false;
        }
    }
    return true;
}

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
bool check_circular_rotation(vector<vector<int>> a)
{
    int n = a.size(), m = a[0].size();
    // if there is only one row or one column in matrix then return true
    if (n == 1 || m == 1)
        return true;

    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            // checking for element present at upper left diagonal of matrix
            if (a[i][j] != a[i - 1][j - 1])
                return false;
        }
        // checking for first element of current row and last element of previous row
        if (a[i][0] != a[i - 1][m - 1])
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a;
    for (int i = 0; i < n; i++)
    {
        vector<int> v(m);
        for (int j = 0; j < m; j++)
        {
            cin >> v[j];
        }
        a.push_back(v);
    }
    if (check_circular_rotation(a))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

 

Input

a[4][4] = {10, 20, 30, 40},
          {40, 10, 20, 30},
          {30, 40, 10, 20},
          {20, 30, 40, 10}

 

Output 

Yes

 

Complexity Analysis

Time Complexity 

As you can see, two loops are being used. The outer loop runs from 1 to the row size and the inner loop runs from 1 to the column size, therefore, the overall time complexity would O(row*col) which is approximately equal to  O(n^2).

Space Complexity

Also, it is clear that no extra space has been used in the solution above. Thus, the space complexity for the code mentioned above will be O(1).

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

Frequently Asked Questions

Which data structure is used to form Matrix? Explain it.

A two-dimensional array is such a data structure that is used to form a Matrix. Arrays within the arrays are what we call two-dimensional arrays which are collections of rows and columns.

What is the need for a two-dimensional array?

Data that cannot be stored in a single-dimensional array, that is, the information which requires rows and columns to be stored, managed, and assessed in a one-dimensional array are stored in two-dimensional arrays.

How are two-dimensional arrays stored in memory?

A two-dimensional array in the form of one row following another in the memory in the computer’s memory.

How can we obtain data from a two-dimensional array?

Like one dimensional array, we can obtain data from any individual cell of a two-dimensional array by using the indices of the cells. In two-dimensional arrays, there are two indices attached to each cell in which one index denotes row number, while the other denotes column number.

Conclusion

In this blog, we have discussed the problem of checking circular rotations in every row of the matrix with suitable examples, we have discussed the implementation of the problem in C++, and in the end, we have concluded with the complexities of the approach.

We hope the above discussion helped you understand and solve the problem better and now it is your turn to code the problem in your own way.

If you want to practice problems on the matrix you can refer to these links:

 

For peeps out there who want to grasp more about DSA, Power programming, JavaScript, or any other technical or core topics, you can refer to guided paths on Coding Ninjas Studio. Do enroll in the courses provided by us, take mock tests and solve problems available and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations. 

Do upvote our blog to help fellow ninjas grow.

Happy Coding!

Previous article
Given 1’s, 2’s, 3’s ……k’s Print them in ZigZag way
Next article
Check Diagonal Matrix and Scalar Matrix
Live masterclass