Share my two O(logm + logn) solutions


  • 9
    J

    Solution1:

    Treat the matrix as a sorted list, and use binary search.

    class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target)
        {
            if(matrix.empty())  return false;
            
        	int height = matrix.size();
        	int width = matrix[0].size();
        
        	if(matrix[0][0] > target || matrix[height-1][width-1] < target)	return false;	
        
        	int head = 0,tail = height*width-1;
        	int mid,midRow,midCol;
    
        	while(head <= tail)
        	{
        		mid = (head+tail)/2;
        		midCol = mid%width;
        	    midRow = mid/width;
        		if(matrix[midRow][midCol] < target)
        			head = mid+1;
        		else if(matrix[midRow][midCol] > target)
        			tail = mid-1;
        		else
        			return true;
        	}
        	return false;
        }
    };
    

    Solution2:

    Use binary search for matrix[i][0] to find the row where target is in, and then use binary search for matrix[row][j] to find target. This solution is better because it avoids multiplication overflow(height*width) and / and % while it's complexity is the same as solution1.

    class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix,int target)
        {
            if(matrix.empty())  return false;
            
        	int heigth = matrix.size();
        	int width = matrix[0].size();
        	
        	if(matrix[0][0] > target || matrix[heigth-1][width-1] < target)		return false;
        
        	int head = 0;
        	int tail = heigth-1;
        	int mid;
        	while(head != tail && matrix[tail][0] > target)
        	{
        		mid = (head+tail+1)/2;
        		if(matrix[mid][0] < target)		head = mid;
        		else if(matrix[mid][0] > target)	tail = mid-1;	
        		else 	return true;
        	}
        	int row = tail;
        	head = 0,tail = width-1;
        	while(head <= tail)
        	{
        		mid = (head+tail)/2;
        		if(matrix[row][mid] < target)
        			head = mid + 1;
        		else if(matrix[row][mid] > target)
        			tail = mid -1;
        		else return true;
        	}
        	return false;
        }
    };

  • 0
    L

    How come they have the same time complexity? The first one is O(logm+logn), the second is O(logm*logn)


  • 4
    M

    Nonsense, the first one is O(log(m * n)) = O(log(m) + log(n)) and the second one is O(log(m) + log(n)). They have the same complexity!!


  • 0
    L

    why mid = (head+tail+1)/2; need to plus 1?


  • 0
    C

    I like your 2nd solution, which considered overflow


  • 0

    Same Solution in Java

    public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix.length == 0)  
                return false;
            
        	int heigth = matrix.length;
        	int width = matrix[0].length;
        	
        	if(matrix[0][0] > target || matrix[heigth-1][width-1] < target) 
        	    return false;
        
        	int head = 0, tail = heigth-1, mid;
        	
        	while(head != tail && matrix[tail][0] > target){
        		mid = (head+tail+1)/2;
        		
        		if(matrix[mid][0] < target)		
        		    head = mid;
        		else if(matrix[mid][0] > target)	
        		    tail = mid-1;	
        		else 	
        		    return true;
        	}
        	
        	int row = tail;
        	head = 0; 
        	tail = width-1;
        	
        	while(head <= tail) {
        		mid = (head+tail)/2;
        		if(matrix[row][mid] < target)
        			head = mid + 1;
        		else if(matrix[row][mid] > target)
        			tail = mid -1;
        		else 
        		    return true;
        	}
        	return false;
        }
    

  • 0
    R

    the reason why
    mid=(head+tail+1)/2
    is to deal with the case like this

    [[1],[3]] 
    1
    

    if not plus 1 the head will always stuck at the same place


  • 0
    C
    This post is deleted!

  • 0
    S

    Can somebody tell me why to find a search row this formula is used -

    mid = (head+tail+1)//2 
    

    Instead of

    mid = (head+tail)/2
    

Log in to reply
 

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