## Introduction

This blog covers a matrix problem. Matrices are among the most important and often asked data structures in programming contests and technical interviews. There are various standard matrix problems and techniques. This blog tackles a coding task that involves

searching for an element in an m*n matrix and printing its position.

Recommended Topic, __Array Implementation of Queue__ and __Rabin Karp Algorithm__

### Problem Statement

Ninja has given you a n x n matrix and a number x, determine the position of x in the matrix if it exists. If not, print "Not Found." Every row and column in the specified matrix is sorted in ascending order. The designed algorithm should have a linear time complexity.

### Sample Examples

**Example 1**

**Input**

x=36

**Output**

(2,0)

**Explanation**

The Element at (2,0) in the matrix is 36.

**Example 2**

**Input**

x=21

**Output**

Element Not Found

**Explanation**

The Element is not present in the matrix.

## Brute Force Approach

The approach is to run two nested loops, one iterates through rows and the other through the columns of the matrix. Check each element of the matrix for the enquired element and if found return the index of the element. If at the end of the search, the element is not found, print element is not found.

### Algorithm

1. Run a nested loop, one for iterating every row and one for iterating every column.

2. Check each index for x and output the index of the element if it is found.

3. If the element cannot be found, print "Element not found".

### Implementation

```
// Program to search an element in row-wise
// and column-wise sorted matrix by brute-force approach
#include <bits/stdc++.h>
using namespace std;
int bruteSearch(int matrix[3][3], int p, int x)
{
if (p == 0)
return -1;
// start traversing through the entire matrix
for (int i = 0; i < p; i++)
{
for (int j = 0; j < p; j++)
// if element is found return the index
if (matrix[i][j] == x)
{
cout << "(" << i << ", "
<< j << ")"
<< "\n";
return 1;
}
}
cout << "Element not found\n";
return 0;
}
// Driver code
int main()
{
int matrix[3][3] = {{10, 14, 18},
{22, 26, 30},
{34, 38, 42}};
bruteSearch(matrix, 3, 30);
return 0;
}
```

**Output**

`(1,2)`

#### Time Complexity

The time complexity of the above approach is O(n^{2}) as the solution iterates through every row and column of the matrix.

#### Space Complexity

The program's auxiliary space is O(1) because no additional data structure is involved.