Friday, February 6, 2015

Peak finding in 2D matrix of numbers

Peak in a 2D matrix is defined as an element that is no smaller than any neighboring elements. The neighbor of an element is defined as element is on the same row or same column as the element.

Image there is robot loaded with Google map data, we can use this algorithm to direct the robot to quickly find the hill in any given square in the map. 

Time complexity: O(num_rows * lg (num_cols) )

public static int[] findPeakIn2DMatrix(int[][] matrix){
int rows = matrix.length;
int cols = matrix[0].length;
int start = 0, end = cols -1;
int maxIndex = 0; int mid = 0;
while(start<=end){
mid = (start+end)>>>1;
maxIndex = 0;
for(int i=1; i<rows; i++)
maxIndex = matrix[i][mid]>matrix[maxIndex][mid]?i:maxIndex;
if(mid-1>=0 && matrix[maxIndex][mid-1]>matrix[maxIndex][mid])
end = mid-1;
else if(mid+1<cols && matrix[maxIndex][mid+1]>matrix[maxIndex][mid])
start = mid+1;
else
break;
}
return new int[]{maxIndex, mid};
}

No comments:

Post a Comment