**Brute force approach :**Iterate 2D array and find whether that element is present or not. It's obvious but not a satisfactory solution. Complexity will be O(n^2) .So we can think of something in order of O(logn) or O(n).

we can have several method using binary search or via zig-zag movement of matrix.

**One of best possible solution : (using Zig-zag movement)**

logic behind this is that we will start from

*top right corner of matrix and will reach to bottom left*, so we have three possible option to move on either left , bottom or diagonally. But given matrix is sorted in row and column wise ,so we will drop the idea of moving diagonally here.

Now we can move either in left or bottom which will be decided by comparing key and matrix elements.

Pseudo explanation :

` if ( key == matrix(row,column) ) `

key is found here @ (row,column)

else if(key > matrix(row, column))

Move in column wise , since element which i am looking for must be below the

current elements (since elements are sorted.)

else

Move in left direction

Picture speaks better that text` public class FindAnElementin2DSortedArray { `

public FindAnElementin2DSortedArray() {

super();

}

//zig zag matehod with O(n) complexity

public static boolean findByZigzagMethod(int[][] mat, int m, int n, int key) {

int row = 0, col = n - 1;

while (row < m && col >= 0) {

if (mat[row][col] == key) {

return true; // key==matrix(row, column) so return true.

}

if (mat[row][col] < key)

row++;

else

col--;

}

return false; //control reach here means key not found.

}

public static void main(String[] args) {

FindAnElementin2DSortedArray findAnElementin2DSortedArray = new FindAnElementin2DSortedArray();

int[][] mat = {{2,3,4},{8,12,13},{10,15,18}};

System.out.println(FindAnElementin2DSortedArray.findByZigzagMethod(mat, 3, 3,10));

}

}

Sample output : trueWhen we run this program we find that key is found there and it returns true.

Reference: http://leetcode.com/2010/10/searching-2d-sorted-matrix.html

## 0 comments:

## Post a Comment