IBM Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
why is it better than the regular search through all the elements? The complexity seems to be the same..Since the 2d array has all the rows and columns sorted, there should be algorithm that is using the binary search to solve the problem more efficiently...
@S.Abakumoff: This is actually an optimal solution for a square 2d array, as far as I know. It is O(n) for an n*n matrix. An n*n matrix has n^2 elements, so naive search would be O(n^2). A binary search solution is possible, but it probably wouldn't be as good as you think it would be. You can only get O(nlogn) with typical binary search here, or perhaps O(n) with some clever variant.
okay, got it. I checked the web and found O(log(n!)) solution that involves binary search, but it's not a way better than O(n);
@zyfo2: As far as I know, no faster algorithm than O(n) is known. Please provide specific details if you want to claim a better algorithm.
it also runs in O(n) but slightly better. because the algorithm above doesn't make full use of binary search.
check the links below:
leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
leetcode.com/2010/10/searching-2d-sorted-matrix-part-iii.html
I've seen this page before. The algorithm doesn't come with a proof that its worst-case bound is O(n),although it probably is. It's slightly better in the particular tests that were run, on the particular machine it was tested on.
I believe on average it's slightly better since it cuts down the matrix to half every time while this one eliminates just one column or one row at a time. it's just my thought.
@zyfo2: though it cuts the matrix in half, it creates two sub-cases whereas the algorithm presented in this answer only creates one. You can't compare the two algorithms just by arguing that one of them results in subcases that cut the input in half. The number of subcases is very important too.
There is a provable Omega(n) lower bound for this problem.
The idea being that you can create a matrix such that one of the main diagonals is an arbitrary given set. Querying for some member of that set in that matrix must take Omega(n) time in the worst case, for any algorithm.
For one such construction, given x_1, x_2, ... x_n place them in positions M[n][1], M[n-1][2], M[n-2][3],.., M[1][n] (M is matrix and M[i][j] is element of row i, column j).
Now chose Theta(n^2) numbers, all < min x_i, an arrange them so that the top left half of the matrix satisfies the condition, by filling row by and row, and starting with the smallest.
Similarly the bottom right right half can be filled to satify the properties.
Any element finding algorithm, must take Omega(n) in the worst case.
Python version of the O(N) algorithm:
def search(m, v):
# Search for v in a matrix where
# it is guaranteed that
# m[r+1][c] >= m[r][c] and
# m[r][c+1] >= m[r][c]
# Start in the upper right corner
# and go left or down.
r = 0
c = len(m[0]) - 1
while True:
if m[r][c] == v:
return (r, c)
if v < m[r][c]:
# go left (column eliminated)
c -= 1
if c < 0: return None
else:
# go down (row eliminated)
r += 1
if r >= len(m): return None
test_matrix = [
[1, 2, 3, 14, 20],
[4, 6, 10, 15, 30],
[5, 7, 12, 16, 42],
[8, 9, 13, 27, 43],
]
for r in range(len(test_matrix)):
for c in range(len(test_matrix)):
v = test_matrix[r][c]
assert search(test_matrix, v) == (r, c)
assert search(test_matrix, 99) is None
Very nice. I think it is better than O(n). In any case we are checking at most (m+n-1) number of elements we are checking, where m is number of rows and n is number of columns. Please correct me, if I am wrong
@dadakhalandhar: it can't be better than O(n) if it involves checking m + n -1 elements. Just checking n elements is already O(n).
Sorry I messed in up the notations. I mean to say if the 2d array has r rows and c columns then it is O(r+c-1). Please correct me if I am wrong
Yes, if N is the total number of elements, the algorithm is O(sqrt(N)) for a square matrix. The analysis that concluded this algo was O(N) had N as the number of rows in a square matrix, and there are sqrt(number of elements) rows in a square matrix.
In the problem what mentioned is "monotonically sorted 2D array", but not mentioned array is square. Thus the order is O(max(r,c)), where r is # of rows, # of columns.
@Anonymous: Agreed that the algorithm will work for an arbitrary rectangular matrix. The complexity analysis was just for the square matrix case. Also agreed that the complexity for the rectangular case is O(max(r,c)), or equivalently O(r + c).
To clarify, I am defining N as the perimeter of the rectangle. The algorithm does not depend on it being a square. At worst it does m+m comparisons (N/2), which makes it O(N).
Suppose I have [1 2 5 13 16 18 25; 4 6 7 14 17 19 31; 10 12 15 16 18 33 35] and I want to search 15, I will compare with the middle element i.e., 14 and 15 is greater than 14 so I know that it cannot be in the quadrient that is less than or equal to 14 ([1 2 5 13; 4 6 7 14]). So will left with remaing 3 Quadrients. We will do it recurssively.
class BinarySearch_2D
{
public static void main(String args[])
{
int arr[][]=new int[][]{{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}};
int flag =0, search=249;
for(int i=0;i<arr.length;i++)
{
int n = arr[i].length;
int first = 0;
int last = n - 1;
int middle = (first + last)/2;
while( first <= last )
{
if ( arr[i][middle] < search )
first = middle + 1;
else if ( arr[i][middle] == search )
{
flag=1;
System.out.println(search + " is found at [" + (i+1)+"]["+(middle + 1) + "].");
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
}
if(flag==0)
System.out.println("Elemnt is not found");
}
}
public static boolean search(int target, int startL, int startR,
int[][] array, int len) {
for (int i = startL; i < array.length; i++) {
for (int k = startR; k < len; k++) {
if (target == array[i][k]) {
return true;
} else if ((k == (len - 1)) && (target < array[i][k])) {
len--;
break;
} else if ((k == (len - 1)) && (target > array[i][k])) {
startR = k;
break;
}
}
}
return false;
}
Here is divide & conquer algorithm. I believe it has logarithmic complexity, because on each step we discard at least quarter of elements. Code in C#:
static bool Find(int[,] arr, int value, int xmin, int ymin, int xmax, int ymax)
{
if (xmin > xmax || ymin > ymax) return false;
int pivotX = (xmin + xmax) / 2, pivotY = (ymin + ymax) / 2;
if (value < arr[pivotX, pivotY])
return
Find(arr, value, xmin, ymin, xmax, pivotY - 1) ||
Find(arr, value, xmin, pivotY, pivotX - 1, ymax);
if (value > arr[pivotX, pivotY])
return
Find(arr, value, xmin, pivotY + 1, xmax, ymax) ||
Find(arr, value, pivotX + 1, ymin, xmax, pivotY);
return true;
}
static bool Find(int[,] arr, int value)
{
return Find(arr, value, 0, 0, arr.GetLength(0) - 1, arr.GetLength(1) - 1);
}
static void Main(string[] args)
{
int[,] arr = new int[,]
{
{ 1, 2, 3, 14, 20 },
{ 4, 6, 10, 15, 30 },
{ 5, 7, 12, 16, 42 },
{ 8, 9, 13, 27, 43 }
};
Console.WriteLine(Find(arr, 19)); // false
Console.WriteLine(Find(arr, 27)); // true
}
- Ali February 11, 2013public static boolean isNumberInSorted2DArray(int[][] array, int element, int numberofRows, int numberOfcols) { int low = 0, high = numberOfcols -1; while(low < numberOfcols && high >= 0) { if(array[low][high] == element) return true; if(element > array[low][high]) low++; else high--; } return false; }