Posted on by Kalkicode
Code Matrix

# Search element in row and column sorted matrix

The problem is to search for a given element in a row and column sorted matrix. The matrix is sorted in such a way that elements in each row are sorted in ascending order from left to right, and elements in each column are sorted in ascending order from top to bottom. The goal is to efficiently determine whether a given element exists in the matrix and if so, provide its location.

## Example

Consider the following sorted matrix:

``````  8   9  12  17  30  37  50  90
10  16  21  33  40  44  65  93
15  18  32  36  43  59  70  97
19  29  38  49  52  62  75  99
28  39  42  51  61  69  78 117
31  55  80  85  96 108 120 170``````

In this matrix, we want to search for elements like 51, 36, 117, and 16. The program should correctly identify whether these elements exist in the matrix and provide their respective locations.

## Idea to Solve the Problem

To solve this problem efficiently, we can start the search from the top right corner of the matrix. Here's the idea behind this approach:

1. Start at the top right corner `(i=0, j=C-1)` of the matrix.
2. If the element at the current position `(i, j)` is equal to the target element, then we have found the element.
3. If the element at the current position is greater than the target element, we move to the left (decrease column index `j`).
4. If the element at the current position is less than the target element, we move downwards (increase row index `i`).

We continue this process until we find the element or exhaust all possibilities.

## Pseudocode

``````searchElement(matrix, element):
i = 0
j = C - 1
a = -1
b = -1
while (a == -1 && b == -1) and (i < R and j >= 0):
if matrix[i][j] == element:
a = i
b = j
else if matrix[i][j] > element:
j--
else:
i++
if a != -1 and b != -1:
print element, "element exist at location (", a, ",", b, ")"
else:
print element, "element not exists"

main:
matrix = ...  // Define the matrix
searchElement(matrix, 51)
searchElement(matrix, 36)
searchElement(matrix, 117)
searchElement(matrix, 16)``````

## Code Solution

``````// C Program
// Search element in row and column sorted matrix
#include <stdio.h>

// Matrix size
#define R 6
#define C 8
// Find given element in sorted row and column matrix
void searchElement(int matrix[R][C], int element)
{
int i = 0;
int j = C - 1;
// This is Used to detect resultant element location
int a = -1;
int b = -1;
// Find element from top right corner
while ((a == -1 && b == -1) && i < R && j >= 0)
{
if (matrix[i][j] == element)
{
// When we get result
a = i;
b = j;
}
else if (matrix[i][j] > element)
{
// reduce the column position
j--;
}
else
{
// increase the row
i++;
}
}
if (a != -1 && b != -1)
{
printf(" %d element exist at location (%d,%d) \n", element, a, b);
}
else
{
printf(" %d element not exists\n", element);
}
}
int main(int argc, char
const *argv[])
{
// Matrix which is sorted row and column wise
int matrix[R][C] =
{
{ 8,  9,  12, 17, 30, 37, 50, 90 },
{ 10, 16, 21, 33, 40, 44, 65, 93 },
{ 15, 18, 32, 36, 43, 59, 70, 97 },
{ 19, 29, 38, 49, 52, 62, 75, 99 },
{ 28, 39, 42, 51, 61, 69, 78, 117 },
{ 31, 55, 80, 85, 96, 108, 120, 170 },
};
// Test case
searchElement(matrix, 51);
searchElement(matrix, 36);
searchElement(matrix, 117);
searchElement(matrix, 16);
return 0;
}``````

#### Output

`````` 51 element exist at location (4,3)
36 element exist at location (2,3)
117 element exist at location (4,7)
16 element exist at location (1,1)``````
``````/*
Java Program for
Search element in row and column sorted matrix
*/
class Searching
{
// Find given element in sorted row and column matrix
public void searchElement(int[][] matrix, int element)
{
// Get the size
int rows = matrix.length;
int cols = matrix[0].length;
int i = 0;
int j = cols - 1;
// This is Used to detect resultant element location
int a = -1;
int b = -1;
// Find element from top right corner
while ((a == -1 && b == -1) && i < rows && j >= 0)
{
if (matrix[i][j] == element)
{
// When we get result
a = i;
b = j;
}
else if (matrix[i][j] > element)
{
// reduce the column position
j--;
}
else
{
// increase the row
i++;
}
}
if (a != -1 && b != -1)
{
// When result exists
System.out.print(" " + element + " element exist at location (" + a + "," + b + ") \n");
}
else
{
System.out.print(" " + element + " element not exists\n");
}
}
public static void main(String[] args)
{
// Matrix which is sorted row and column wise
int[][] matrix =
{
{ 8,  9,  12, 17, 30, 37, 50, 90 },
{ 10, 16, 21, 33, 40, 44, 65, 93 },
{ 15, 18, 32, 36, 43, 59, 70, 97 },
{ 19, 29, 38, 49, 52, 62, 75, 99 },
{ 28, 39, 42, 51, 61, 69, 78, 117 },
{ 31, 55, 80, 85, 96, 108, 120, 170 }
};
// Test case
}
}``````

#### Output

`````` 51 element exist at location (4,3)
36 element exist at location (2,3)
117 element exist at location (4,7)
16 element exist at location (1,1)``````
``````// Include header file
#include <iostream>
// Matrix size
#define R 6
#define C 8
using namespace std;
/*
C++ Program for
Search element in row and column sorted matrix
*/
class Searching
{
public:
// Find given element in sorted row and column matrix
void searchElement(int matrix[R][C], int element)
{
int i = 0;
int j = C - 1;
// This is Used to detect resultant element location
int a = -1;
int b = -1;
// Find element from top right corner
while ((a == -1 && b == -1) && i < R && j >= 0)
{
if (matrix[i][j] == element)
{
// When we get result
a = i;
b = j;
}
else if (matrix[i][j] > element)
{
// reduce the column position
j--;
}
else
{
// increase the row
i++;
}
}
if (a != -1 && b != -1)
{
// When result exists
cout << " " << element << " element exist at location (" << a << "," << b << ") \n";
}
else
{
cout << " " << element << " element not exists\n";
}
}
};
int main()
{
// Matrix which is sorted row and column wise
int matrix[R][C] =
{
{ 8,  9,  12, 17, 30, 37, 50, 90 },
{ 10, 16, 21, 33, 40, 44, 65, 93 },
{ 15, 18, 32, 36, 43, 59, 70, 97 },
{ 19, 29, 38, 49, 52, 62, 75, 99 },
{ 28, 39, 42, 51, 61, 69, 78, 117 },
{ 31, 55, 80, 85, 96, 108, 120, 170 }
};
// Test case
return 0;
}``````

#### Output

`````` 51 element exist at location (4,3)
36 element exist at location (2,3)
117 element exist at location (4,7)
16 element exist at location (1,1)``````
``````// Include namespace system
using System;
/*
C# Program for
Search element in row and column sorted matrix
*/
public class Searching
{
// Find given element in sorted row and column matrix
public void searchElement(int[,] matrix, int element)
{
// Get the size
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);
int i = 0;
int j = cols - 1;
// This is Used to detect resultant element location
int a = -1;
int b = -1;
// Find element from top right corner
while ((a == -1 && b == -1) && i < rows && j >= 0)
{
if (matrix[i,j] == element)
{
// When we get result
a = i;
b = j;
}
else if (matrix[i,j] > element)
{
// reduce the column position
j--;
}
else
{
// increase the row
i++;
}
}
if (a != -1 && b != -1)
{
// When result exists
Console.Write(" " + element + " element exist at location (" + a + "," + b + ") \n");
}
else
{
Console.Write(" " + element + " element not exists\n");
}
}
public static void Main(String[] args)
{
// Matrix which is sorted row and column wise
int[,] matrix = {
{
8 , 9 , 12 , 17 , 30 , 37 , 50 , 90
} , {
10 , 16 , 21 , 33 , 40 , 44 , 65 , 93
} , {
15 , 18 , 32 , 36 , 43 , 59 , 70 , 97
} , {
19 , 29 , 38 , 49 , 52 , 62 , 75 , 99
} , {
28 , 39 , 42 , 51 , 61 , 69 , 78 , 117
} , {
31 , 55 , 80 , 85 , 96 , 108 , 120 , 170
}
};
// Test case
}
}``````

#### Output

`````` 51 element exist at location (4,3)
36 element exist at location (2,3)
117 element exist at location (4,7)
16 element exist at location (1,1)``````
``````<?php
/*
Php Program for
Search element in row and column sorted matrix
*/
class Searching
{
// Find given element in sorted row and column matrix
public  function searchElement( & \$matrix, \$element)
{
// Get the size
\$rows = count(\$matrix);
\$cols = count(\$matrix[0]);
\$i = 0;
\$j = \$cols - 1;
// This is Used to detect resultant element location
\$a = -1;
\$b = -1;
// Find element from top right corner
while ((\$a == -1 && \$b == -1) && \$i < \$rows && \$j >= 0)
{
if (\$matrix[\$i][\$j] == \$element)
{
// When we get result
\$a = \$i;
\$b = \$j;
}
else if (\$matrix[\$i][\$j] > \$element)
{
// reduce the column position
\$j--;
}
else
{
// increase the row
\$i++;
}
}
if (\$a != -1 && \$b != -1)
{
// When result exists
echo " ". \$element ." element exist at location (". \$a .",". \$b .") \n";
}
else
{
echo " ". \$element ." element not exists\n";
}
}
}

function main()
{
// Matrix which is sorted row and column wise
\$matrix = array(
array(8, 9, 12, 17, 30, 37, 50, 90),
array(10, 16, 21, 33, 40, 44, 65, 93),
array(15, 18, 32, 36, 43, 59, 70, 97),
array(19, 29, 38, 49, 52, 62, 75, 99),
array(28, 39, 42, 51, 61, 69, 78, 117),
array(31, 55, 80, 85, 96, 108, 120, 170)
);
// Test case
}
main();``````

#### Output

`````` 51 element exist at location (4,3)
36 element exist at location (2,3)
117 element exist at location (4,7)
16 element exist at location (1,1)``````
``````/*
Node Js Program for
Search element in row and column sorted matrix
*/
class Searching
{
// Find given element in sorted row and column matrix
searchElement(matrix, element)
{
// Get the size
var rows = matrix.length;
var cols = matrix[0].length;
var i = 0;
var j = cols - 1;
// This is Used to detect resultant element location
var a = -1;
var b = -1;
// Find element from top right corner
while ((a == -1 && b == -1) && i < rows && j >= 0)
{
if (matrix[i][j] == element)
{
// When we get result
a = i;
b = j;
}
else if (matrix[i][j] > element)
{
// reduce the column position
j--;
}
else
{
// increase the row
i++;
}
}
if (a != -1 && b != -1)
{
// When result exists
process.stdout.write(" " + element + " element exist at location (" + a + "," + b + ") \n");
}
else
{
process.stdout.write(" " + element + " element not exists\n");
}
}
}

function main()
{
// Matrix which is sorted row and column wise
var matrix = [
[8, 9, 12, 17, 30, 37, 50, 90] ,
[10, 16, 21, 33, 40, 44, 65, 93] ,
[15, 18, 32, 36, 43, 59, 70, 97] ,
[19, 29, 38, 49, 52, 62, 75, 99] ,
[28, 39, 42, 51, 61, 69, 78, 117] ,
[31, 55, 80, 85, 96, 108, 120, 170]
];
// Test case
}
main();``````

#### Output

`````` 51 element exist at location (4,3)
36 element exist at location (2,3)
117 element exist at location (4,7)
16 element exist at location (1,1)``````
``````#   Python 3 Program for
#   Search element in row and column sorted matrix

class Searching :
#  Find given element in sorted row and column matrix
def searchElement(self, matrix, element) :
#  Get the size
rows = len(matrix)
cols = len(matrix[0])
i = 0
j = cols - 1
#  This is Used to detect resultant element location
a = -1
b = -1
#  Find element from top right corner
while ((a == -1 and b == -1) and i < rows and j >= 0) :
if (matrix[i][j] == element) :
#  When we get result
a = i
b = j

elif(matrix[i][j] > element) :
#  reduce the column position
j -= 1
else :
#  increase the row
i += 1

if (a != -1 and b != -1) :
#  When result exists
print(" ", element ," element exist at location (", a ,",", b ,") ")
else :
print(" ", element ," element not exists")

def main() :
#  Matrix which is sorted row and column wise
matrix = [
[8, 9, 12, 17, 30, 37, 50, 90] , [10, 16, 21, 33, 40, 44, 65, 93] , [15, 18, 32, 36, 43, 59, 70, 97] , [19, 29, 38, 49, 52, 62, 75, 99] , [28, 39, 42, 51, 61, 69, 78, 117] , [31, 55, 80, 85, 96, 108, 120, 170]
]
#  Test case

if __name__ == "__main__": main()``````

#### Output

``````  51  element exist at location ( 4 , 3 )
36  element exist at location ( 2 , 3 )
117  element exist at location ( 4 , 7 )
16  element exist at location ( 1 , 1 )``````
``````#   Ruby Program for
#   Search element in row and column sorted matrix

class Searching
#  Find given element in sorted row and column matrix
def searchElement(matrix, element)
#  Get the size
rows = matrix.length
cols = matrix[0].length
i = 0
j = cols - 1
#  This is Used to detect resultant element location
a = -1
b = -1
#  Find element from top right corner
while ((a == -1 && b == -1) && i < rows && j >= 0)
if (matrix[i][j] == element)
#  When we get result
a = i
b = j
elsif(matrix[i][j] > element)
#  reduce the column position
j -= 1
else
#  increase the row
i += 1
end

end

if (a != -1 && b != -1)
#  When result exists
print(" ", element ," element exist at location (", a ,",", b ,") \n")
else
print(" ", element ," element not exists\n")
end

end

end

def main()
#  Matrix which is sorted row and column wise
matrix = [
[8, 9, 12, 17, 30, 37, 50, 90] ,
[10, 16, 21, 33, 40, 44, 65, 93] ,
[15, 18, 32, 36, 43, 59, 70, 97] ,
[19, 29, 38, 49, 52, 62, 75, 99] ,
[28, 39, 42, 51, 61, 69, 78, 117] ,
[31, 55, 80, 85, 96, 108, 120, 170]
]
#  Test case
end

main()``````

#### Output

`````` 51 element exist at location (4,3)
36 element exist at location (2,3)
117 element exist at location (4,7)
16 element exist at location (1,1)
``````
``````/*
Scala Program for
Search element in row and column sorted matrix
*/
class Searching
{
// Find given element in sorted row and column matrix
def searchElement(matrix: Array[Array[Int]], element: Int): Unit = {
// Get the size
var rows: Int = matrix.length;
var cols: Int = matrix(0).length;
var i: Int = 0;
var j: Int = cols - 1;
// This is Used to detect resultant element location
var a: Int = -1;
var b: Int = -1;
// Find element from top right corner
while ((a == -1 && b == -1) && i < rows && j >= 0)
{
if (matrix(i)(j) == element)
{
// When we get result
a = i;
b = j;
}
else if (matrix(i)(j) > element)
{
// reduce the column position
j -= 1;
}
else
{
// increase the row
i += 1;
}
}
if (a != -1 && b != -1)
{
// When result exists
print(" " + element + " element exist at location (" + a + "," + b + ") \n");
}
else
{
print(" " + element + " element not exists\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Searching = new Searching();
// Matrix which is sorted row and column wise
var matrix: Array[Array[Int]] = Array(
Array(8, 9, 12, 17, 30, 37, 50, 90),
Array(10, 16, 21, 33, 40, 44, 65, 93),
Array(15, 18, 32, 36, 43, 59, 70, 97),
Array(19, 29, 38, 49, 52, 62, 75, 99),
Array(28, 39, 42, 51, 61, 69, 78, 117),
Array(31, 55, 80, 85, 96, 108, 120, 170)
);
// Test case
}
}``````

#### Output

`````` 51 element exist at location (4,3)
36 element exist at location (2,3)
117 element exist at location (4,7)
16 element exist at location (1,1)``````
``````/*
Swift 4 Program for
Search element in row and column sorted matrix
*/
class Searching
{
// Find given element in sorted row and column matrix
func searchElement(_ matrix: [[Int]], _ element: Int)
{
// Get the size
let rows: Int = matrix.count;
let cols: Int = matrix[0].count;
var i: Int = 0;
var j: Int = cols - 1;
// This is Used to detect resultant element location
var a: Int = -1;
var b: Int = -1;
// Find element from top right corner
while ((a == -1 && b == -1) && i < rows && j >= 0)
{
if (matrix[i][j] == element)
{
// When we get result
a = i;
b = j;
}
else if (matrix[i][j] > element)
{
// reduce the column position
j -= 1;
}
else
{
// increase the row
i += 1;
}
}
if (a  != -1 && b  != -1)
{
// When result exists
print(" ", element ," element exist at location (", a ,",", b ,") ");
}
else
{
print(" ", element ," element not exists");
}
}
}
func main()
{
// Matrix which is sorted row and column wise
let matrix: [[Int]] = [
[8, 9, 12, 17, 30, 37, 50, 90] ,
[10, 16, 21, 33, 40, 44, 65, 93] ,
[15, 18, 32, 36, 43, 59, 70, 97] ,
[19, 29, 38, 49, 52, 62, 75, 99] ,
[28, 39, 42, 51, 61, 69, 78, 117] ,
[31, 55, 80, 85, 96, 108, 120, 170]
];
// Test case
}
main();``````

#### Output

``````  51  element exist at location ( 4 , 3 )
36  element exist at location ( 2 , 3 )
117  element exist at location ( 4 , 7 )
16  element exist at location ( 1 , 1 )``````
``````/*
Kotlin Program for
Search element in row and column sorted matrix
*/
class Searching
{
// Find given element in sorted row and column matrix
fun searchElement(matrix: Array <Array <Int>> , element: Int): Unit
{
// Get the size
var rows: Int = matrix.count();
var cols: Int = matrix[0].count();
var i: Int = 0;
var j: Int = cols - 1;
// This is Used to detect resultant element location
var a: Int = -1;
var b: Int = -1;
// Find element from top right corner
while ((a == -1 && b == -1) && i < rows && j >= 0)
{
if (matrix[i][j] == element)
{
// When we get result
a = i;
b = j;
}
else if (matrix[i][j] > element)
{
// reduce the column position
j -= 1;
}
else
{
// increase the row
i += 1;
}
}
if (a != -1 && b != -1)
{
// When result exists
print(" " + element + " element exist at location (" + a + "," + b + ") \n");
}
else
{
print(" " + element + " element not exists\n");
}
}
}
fun main(args: Array < String > ): Unit
{
// Matrix which is sorted row and column wise
var matrix: Array <Array<Int>> = arrayOf(
arrayOf(8, 9, 12, 17, 30, 37, 50, 90),
arrayOf(10, 16, 21, 33, 40, 44, 65, 93),
arrayOf(15, 18, 32, 36, 43, 59, 70, 97),
arrayOf(19, 29, 38, 49, 52, 62, 75, 99),
arrayOf(28, 39, 42, 51, 61, 69, 78, 117),
arrayOf(31, 55, 80, 85, 96, 108, 120, 170)
);
// Test case
}``````

#### Output

`````` 51 element exist at location (4,3)
36 element exist at location (2,3)
117 element exist at location (4,7)
16 element exist at location (1,1)``````

## Output Explanation

The mentioned C code implements the above approach to search for the given elements in the sorted matrix. It correctly identifies whether each element exists in the matrix and provides their respective locations if they are present. The output matches the expected locations for each searched element.

## Time Complexity

The time complexity of the mentioned solution is O(R + C), where R is the number of rows and C is the number of columns in the matrix. In the worst case, we may start at the top right corner and traverse either the entire row or the entire column to find the element. Therefore, the time complexity is O(R + C).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post