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