Solutions in O(m*n) time complexity should be accepted?

• My solution has O(m*n) time complexity, and it was accepted. I think that the test suite needs some revising.

``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == target) {
return true;
}
}
}

return false;
}
}``````

• As mentioned in question that rows are sorted so you can use binary search in rows.
it can be done O(m*log n).

• a better idea is: we can treat the two-dimension array as an one-dimension array because the elements in each are in increasing order, so that we can use binary search to optimize the solution:

``````public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int start = 0;
int end = m * n - 1;

while (start <= end) {
int mid = start + (end - start) / 2;
int val = matrix[mid / n][mid % n];  // get the middle element in "one-dimension" array
if (target == val) {
return true;
} else if (target > val) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return false;
}
``````

the run-time complexity should be O(log(m*n)), m number of rows and n is number of columns.

• I am aware that this is not the optimum solution, I am just surprised that an O(m*n) time complexity solution is accepted. My questions raises a flag about the test suite used for the submissions -- it is not sufficiently well constructed.

• I am aware that this is not the optimum solution, I am just surprised that an O(m*n) time complexity solution is accepted. My questions raises a flag about the test suite used for the submissions -- it is not sufficiently well constructed.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.