My solution in O(n) time. Can be optimized to O(min(log(n),log(m)))


  • -1
    A
    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0)
            return false;
        
        int rowToSearch = -1;
        
        for(int i = 0; i < matrix.length; i++){
            if(target == matrix[i][0]){
                return true;
            }
            else if(target > matrix[i][0]){
                rowToSearch++;
            }
        }
        
        if(rowToSearch < 0)
            return false;
        
        int index = Arrays.binarySearch(matrix[rowToSearch], target);
        if(index > 0) {
            return true;
        }
        else {
            return false;
        }
    } 
    

    }

    explanation : check if target is equal to the first element of every row. if it is return true since we have found the number. if it is greater we must compare every first element of each row and stop when we find a target that is less than the first element of that row. the target must lie in the previous row.
    Since it is sorted we can do a binary search in that row in log(n) time. since the two loops are separate the worst case is O(n) since the worst case is the one where the target is in the last row which means we made n comparisons and searched the last row in log(n) comparisons.


  • 1
    D

    Overall complexity of your algorithm is O(n + logn) which is O(n). You search for a row in linear time and do a binary search.


  • 0
    A

    you are right. i will edit the post.


  • 0
    S

    How could you improve to O(min(logm, logn))?


  • 0
    A

    by doing a binary search on the column instead of doing a linear traversal of the column to find the row in which the elements lies.


Log in to reply
 

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