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


  • 3
    D

    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;
        }
    }

  • 0
    D

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


  • 4
    Z

    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.


  • 0
    D

    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.


  • 0
    D

    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.


Log in to reply
 

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