## Find an element in a matrix whose rows and columns are sorted

Given a matrix in which each row and each column is sorted, write a method to find an element in it.

My initial thoughts:
We are kind-of doing a 2D binary search here. Each time we find the center of the matrix. If that is the element we are looking for, then return it. Notice that the center divide the matrix into four parts: upper-left, upper-right, bottom-left and bottom-right. If the element we are looking for is less than the center, then it cannot be in the bottom-right part, where every elements are even greater than the center. If the element we are searching is greater than the center, then it cannot be in the upper-left part. Hence, each time we approximately eliminate $\frac{1}{4}$ of the entire matrix. Therefore we have the recursion: $T(n)=3T(n/4)+O(1)$, whose solution is $O(n)=n^{0.75}$.

My initial codes:

	public static Pair<Integer> findInMatrix(int[][] data, int rowLow,
int rowHigh, int colLow, int colHigh, int element) {
if (rowLow > rowHigh || colLow > colHigh)
return null;
new LinkedList<Pair<Integer>>();
int rowMid = (rowLow + rowHigh) / 2;
int colMid = (colLow + colHigh) / 2;
int mid = data[rowMid][colMid];
if (mid == element)
return new Pair<Integer>(rowMid, colMid);
else if (element < mid) {
Pair<Integer> topLeft = findInMatrix(data, rowLow, rowMid - 1,
colLow, colMid - 1, element);
if (topLeft == null) {
Pair<Integer> topRight = findInMatrix(data, rowLow, rowMid - 1,
colMid, colHigh, element);
if (topRight == null) {
Pair<Integer> bottomLeft = findInMatrix(data, rowMid,
rowHigh, colLow, colMid - 1, element);
return bottomLeft;
} else
return topRight;
} else
return topLeft;
} else { // element > mid
Pair<Integer> topRight = findInMatrix(data, rowLow, rowMid - 1,
colMid + 1, colHigh, element);
if (topRight == null) {
Pair<Integer> bottomLeft = findInMatrix(data, rowMid + 1,
rowHigh, colLow, colMid, element);
if (bottomLeft == null) {
Pair<Integer> bottomRight = findInMatrix(data, rowMid,
rowHigh, colMid + 1, colHigh, element);
return bottomRight;
} else
return bottomLeft;
} else
return topRight;
}
}

Solution:
This algorithm works by elimination. Every move to the left (–col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row.
public static Pair<Integer> FindElem(int[][] mat, int elem, int M, int N) {
int row = 0;
int col = N - 1;
while (row < M && col >= 0) {
if (mat[row][col] == elem) {
return new Pair<Integer>(row, col);
} else if (mat[row][col] > elem) {
col--;
} else {
row++;
}
}
return null;
}

Comments: Brilliant. Time complexity $O(m+n)$.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5adbaa5eb09e1', {
sectionId: '370373',
format: 'inread'
});
});

Advertisements

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5adbaa5eb0a0c',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5adbaa5eb0a0e',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Like this:Like Loading...

Related


### 1 Comment (+add yours?)

1. Szilard
Dec 16, 2013 @ 15:50:06

Hi,

Initially, I had the same idea as yours but it has a complexity of O( (n*m) ^ (log4(3))) which is approximately O((n*m)^0.8).

The space is actually n*m and not n as you noted in the formula and used master theorem to devise its complexity.

The proposed solution is O(n+m) which is clearly a better choice asymptotically.

I wonder how the generalized problem can be solved. (when we have more dimensions and the elements are sorted on each dimension. e.g. a cube of numbers)