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

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;
}

You can also try this code with Online C++ Compiler

Run Code

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;
    }
}

You can also try this code with Online C++ Compiler

Run Code

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).