## xyz Interview Question

Developer Program Engineers**Country:**United States

**Interview Type:**Phone Interview

There are surprisingly 4 solutions to this problem! We can start with the brute force and improve from O(n^2) -> O(nlogn) -> O(n) -> O(lgn). I have outlined the 4 solutions below with explanations.

PS:- I would appreciate if you can plz upvote :P, I put in some effort to clearly explain the solution. :P

Python solution:

```
# Brute Force - Look at each element one by one
# O(n^2) solution
def searchVersion1(matrix, target):
for i, row in enumerate(matrix):
for j, sq in enumerate(row):
if sq == target:
return True
return False
# Since each row is sorted, perform binary search
# Since there are n rows, the runtime is O(n*lgn)
def searchVersion2(matrix, target):
def binarySearchHelper(row, target, low, high):
while low <= high:
mid = (low + high) // 2
if row[mid] == target:
return True
elif row[mid] < target:
low = mid + 1
elif row[mid] > target:
high = mid - 1
return False
for i, row in enumerate(matrix):
if binarySearchHelper(row, target, 0, len(row)-1):
return True
return False
# O(n) solution
# We can start from top-right corner of the matrix
# and move up to bottom right. If current element < target, move down
# else if element > target, move left. If we go out of bounds, we can
# return False since the element is not found.
def searchVersion3(matrix, target):
x, y = 0, len(matrix[0])-1
while 0 <= x < len(matrix) and 0 <= y < len(matrix[0]):
currentElement = matrix[x][y]
if currentElement == target:
return True
elif currentElement < target:
x += 1 # Move down
elif currentElement > target:
y -= 1 # Move left
return False
# O(lgn) solution
# Treat the 2-d matrix as a 1-d sorted array
# and just map the indices using math while applying binary search.
def searchVersion4(matrix, target):
rows, cols = len(matrix), len(matrix[0])
low, high = 0, rows * cols - 1
while low <= high:
mid = (low + high) // 2
curRow = mid // cols
curCol = mid % cols
currentElement = matrix[curRow][curCol]
if currentElement == target:
return True
elif currentElement < target:
low = mid + 1
else:
high = mid - 1
return False
matrix = \
[
[1 , 3, 5, 7, 9] ,
[11,13,15,16,20],
[21,22,23,24,25],
[30,32,35,40,45],
]
print(searchVersion1(matrix, 23)) # True
print(searchVersion1(matrix, 28)) # False
print(searchVersion1(matrix, 5)) # True
print(searchVersion1(matrix, 10))# False
print('#' * 20)
print(searchVersion2(matrix, 23))# True
print(searchVersion2(matrix, 28))# False
print(searchVersion2(matrix, 5))# True
print(searchVersion2(matrix, 10))# False
print('#' * 20)
print(searchVersion3(matrix, 23))# True
print(searchVersion3(matrix, 28))# False
print(searchVersion3(matrix, 5))# True
print(searchVersion3(matrix, 10))# False
print('#' * 20)
print(searchVersion4(matrix, 23))# True
print(searchVersion4(matrix, 28))# False
print(searchVersion4(matrix, 5))# True
print(searchVersion4(matrix, 10))# False
```

Binary search to find the row and binary search to find the element in the row, log(n) + log(n). Complexity should be log(n).

- Biswanath March 06, 2018