The issue states that we are presented with an integer, ```
// code for finding the row and column index of an element in an array
include<bits/stdc++.h>
using namespace std;
// function for finding the position
void Find_Position(int matrix4, int X){
int r = 4, c = 4;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
// checking for matching index
if(matrixi==X){
cout << "The element found At " << i+1 << "," << j+1;
return;
}
}
}
//The element has not been found
cout << "Not Found" << endl;
}
int main{
// given matrix
int matrix4 = { {11, 22, 3, 5},
{9, 46, 7, 8},
{12,1,11,42},
{33,14,25,16} };
// giving the number as input
int X = 8;
//function calling
Find_Position(matrix, X);
}
### Example:
Input:
{ {12, 2, 13, 9},
{58 6, 7, 8},
{9, 11, 61, 62},
{19, 43, 15, 45} }
X = 8 is the element to be discovered.
You have the option to traverse the matrix, starting from the upper left corner (1st row, 1st column), and evaluating each element against the target value (in this scenario, 8).
### Comparison in the first row:
Element at the index 1,1: 1 (Not equal to 8)
Element at the index 1,2: 2 (Not equal to 8)
Element at the index 1,3: 3 (Not equal to 8)
Element at the index1,4: 4 (Not equal to 8)
### In the second row, there is a comparison:
Position 2: 1 Element: 5 (Not equivalent to 8)
Element at the index 2,2: 6 (Not equal to 8)
Element at the index 2,3: 7 (Not equal to 8)
Element at the index 2,4: 8 (Equal to 8)
Output:
As a consequence, element 8 is displayed in row two, column four, at position 2,4.
## Naive Approach
In the Simple approach, we can iterate through the entire matrix that is sorted row by row and column by column to locate the specified element. Once the element is found, we can display its position.
Algorithm StepsL=:
- Run nested for loop , with an outer for loop for the row and an inner for loop for a column .
- If every element and X are equal, display the "Found at": row and column number.
- If an element is missing from the matrix, print "Not Found" .
Filename: Row_col_index.cpp
// code for finding the row and column index of an element in an array
include<bits/stdc++.h>
using namespace std;
// function for finding the position
void Find_Position(int matrix4, int X){
int r = 4, c = 4;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
// checking for matching index
if(matrixi==X){
cout << "The element found At " << i+1 << "," << j+1;
return;
}
}
}
//The element has not been found
cout << "Not Found" << endl;
}
int main{
// given matrix
int matrix4 = { {11, 22, 3, 5},
{9, 46, 7, 8},
{12,1,11,42},
{33,14,25,16} };
// giving the number as input
int X = 8;
//function calling
Find_Position(matrix, X);
}
Output:
The element found At 2,4
### Analysis of Complexity
Time complexity: O(R*C)
In this context, R represents the total number of rows in a matrix sorted both row-wise and column-wise, while C denotes the total number of columns in the same matrix following row-wise and column-wise sorting. The time complexity of the program is O(R*C) due to the need to iterate through the entire array during execution.
Space Complexity: O(1)
Elaboration: Extra space is unnecessary.
## Greedy Approach (Optimized)
The objective is to delete rows or columns in each comparison until we reach the necessary number or are beyond the range. We'll begin at the top right corner of the matrix. There are three possible ways for this approach.
- Suppose Element X exceeds the current number. In that scenario, it signifies that all of the components in the current row are less than X (since the row has been arranged and we are in the correct place); we may skip the current row and continue to the next row to get the number X . If Element X is less than the current value. In that scenario, it signifies that all of the components in the current column (column is sorted, and we are at the bottom) are bigger than X. Therefore, we may skip the current column and go to the previous column to find the number.
- If Element X equals the current number, print "The element found at" row and column numbers, and then our search is over.
- In this manner, we can search in a row-wise and column-wise sorted matrix.
Algorithm Steps:
- Let X be the element to be found.
- Create two variables, i = 0 and j = c-1 , representing the 0th row and last columns.
- Repeat until i!= r , where r is the total number of rows or j0.
- If the present number is larger than X , decrease j ; otherwise, increase i if the present number is less than X.
- Print i and j if the element has been found.
- else Print "Not Found" .
Filename: Row_col_index2.cpp
// code for finding the row and column index of an element in an array
include<bits/stdc++.h>
using namespace std;
//function for finding the position
void Find_Position(int matrix4, int x, int r,int c){
int i = 0, j = c-1;
while(i!=r && j>0){
if(matrixi==x){
cout << "The element has been found At " << i+1 << "," << j+1;
return;
}
//If the element's value is greater, proceed to the before column.
if(matrixi>x){
j--;
continue;
}
//If the element's value is less, proceed to the next column.
if(matrixi<x){
i++;
continue;
}
}
// The element has not been found
cout << "Not Found" << endl;
return;
}
int main{
// the initial matrix
int matrix4 = { {1, 2, 3, 4},
{5, 96, 7, 8},
{9,10,11,12},
{13,14,15,17} };
// initializing x value
int X = 8;
// function calling
Find_Position(matrix, X, 4, 4);
}
Output:
The element has been found At 2,4
### Analysis of Complexity
Time complexity: O(N+M)
In this sorted matrix, R represents the total number of rows, while C signifies the total number of columns. The time complexity in the worst-case scenario is O(N+M) as only one row and column are read.
Space Complexity: O(1)
Explanation: Additional space is unnecessary in this context.
