C++ with O(m+n) complexity


  • 55
    L
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (m == 0) return false;
        int n = matrix[0].size();
    
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target)
                return true;
            else if (matrix[i][j] > target) {
                j--;
            } else 
                i++;
        }
        return false;
    }

  • 4
    W

    Just a little tiny improvement - change the order of comparison seems to speed up a little. Cheers~

            if (matrix[i][j] < target)
                i++;
            else if (matrix[i][j] > target)
                j--;
            else
                return true;

  • 3
    W

    I think my solution is log(m)+log(n). Divide the matrix into 4 part, when the middle point is less than target, discard the bottom right part, otherwise if it is greater than target, discard the top left part.

    public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n=matrix.length, m=matrix[0].length;
        return helper(matrix,0,n-1,0,m-1,target);
    }
    boolean helper(int[][] matrix, int rowStart, int rowEnd, int colStart, int colEnd, int target ){
        if(rowStart>rowEnd||colStart>colEnd){
            return false;
        }
        int rm=(rowStart+rowEnd)/2, cm=(colStart+colEnd)/2;
        if(matrix[rm][cm]== target){
            return true;
        }
        else if(matrix[rm][cm] >target){
            return helper(matrix, rowStart, rm-1,colStart, cm-1,target)||
                helper(matrix,  rm, rowEnd, colStart,cm-1,target) ||
                helper(matrix, rowStart, rm-1,cm, colEnd,target);
        }
        else{
            return helper(matrix, rm+1, rowEnd, cm+1,colEnd,target)||
                helper(matrix,  rm+1, rowEnd, colStart,cm,target) ||
                helper(matrix, rowStart, rm,cm+1, colEnd,target);
        }
        
    }
    

    }


  • 0
    S
    This post is deleted!

  • 1

    Your divide-and-conquer solution is dividing the matrix into 4 quadrants and searching in 3 of the quadrants in each recursion. Its runtime complexity can not be log(m) + log(n).

    I have wrote an article which derives the runtime complexity with the restriction of m = n. Basically you have to solve the recurrence relation: T(n) = 3T(n/2) + c, which gives the final complexity around: O(n1.58)


  • 0
    D
    class Solution {
    public:
    	int target;
        bool searchMatrix(vector<vector<int> >& matrix, int target) {
        	this->target = target;
        	int n = matrix.size()-1, m = matrix[0].size()-1;
        	return Find(matrix,0,0,n,m); 
        }
    
        bool Find(vector<vector<int> > &matrix, int i,int j,int n, int m)
        {
        	if(i>n || j>m) return false;
        	int midX = (i+n)>>1, midY = (j+m)>>1;
        	if(matrix[midX][midY] == target) 
        		return true;
        	else if(matrix[midX][midY] > target)
        	{
        		return Find(matrix,i,j,midX-1,midY-1) || Find(matrix,i,midY,midX-1,m)
        		|| Find(matrix,midX,j,n,midY-1);
        	}
        	else
        		return Find(matrix,i,midY+1,midX,m) || Find(matrix,midX+1,j,n,midY)
        		|| Find(matrix,midX+1,midY+1,n,m);
        }
    };
    

    The same code with c++ , get TLE, WHY ??


  • 0
    L

    very smart idea.


  • 0
    S

    Why T(n) = 3T(n/2) + c,?
    I think T(n) = 3T(n/4) + c,
    because it is a 2D matrix, when the edge length is divided by 2, the subproblem size is 1/4...


  • 0
    S

    Hi, 1337c0d3r
    If you still remember the following discussion:

    November 12, 2010 at 11:25 am
    
    You are welcome. BTW, just noticed another thing: O(nlgn) is actually better than O(n^1.58)
    0
    Reply ↓	
    1337c0d3r
    November 14, 2010 at 5:28 pm
    
    You made a very great observation! I need to investigate my code running time why it doesn't reflect this. One speculation is in the quad partition, I use an extra condition
    
    if (l > r || u > d) return false;
    
    to bail out early, while my binary search code does not use this. I will update my findings.
    
    Thanks!
    0
    Reply ↓	
    1337c0d3r
    November 15, 2010 at 12:34 pm
    
    Just to post a follow-up regarding aNiceGuy's observation that O(n lg n) has a lower bound than O(n^1.58), which is true.
    
    The two algorithms (binary search and diagonal binary search) which runs in O(n lg n), runs in a significant longer time than the quad partition method (O(n^1.58).
    
    One way to explain this is that both binary search and diagonal binary search has a higher constant than the quad partition. Also due to N=1000 is not large enough, therefore n^1.58 has not overtake n lg n yet. But if N is large enough, eventually n^1.58 will rise exponentially while n lg n remain pretty flat.
    

    It seems that, quad partition is really faster than n times 1D binary search...So, N^1.58 may not be correct... if applying T(n)=3T(n/4)+c,thinks may be different. Thanks


  • 0
    J

    I think @sydy71 is correct. There are 3 recursive calls, and each call reduce the problem size to 1/4 of the original problem.

    So T(N) <= 3T(N/4) + O(1). Using master theorem, the time complexity is O(N^(log(4,3)), which is approximately O(N^0.79), where N is the total number of elements in the matrix, which is m*n


  • 0

    @sydy71: It depends what you meant by n. Here, we assume m = n (the matrix is a square), and n is the length of the square matrix's side. So, T(n) = 3T(n/2) + c.


  • 0
    S

    Hi, @1337c0d3r Got your point:) , thanks


  • 0

    Smart algorithm. Because every time the upper-right element is the special one: all elements less than it are at its left side and all elements greater than it are behind.


  • 0
    B

    You can firstly do a binary search on diagonal and find two neighboring elements which are less and greater than target. You can thus get rid of the topleft and bottomright submatrix. You then only need to search in the topright and bottom left submatrices. So, n=max(M,N), T(n)=2T(n/2)+log(n), complexity is O(n).


  • 0

    your solution in C++ IS 1500MS but the O(M+N) solution is less than 300 MS .
    so I do think the recursion-method is really time-consuming !!!


  • 0
    S
    This post is deleted!

  • 0
    S

    beats 98%
    '''

        bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if(m<1) return false;
        int n = matrix[0].size();
        if(n<1) return false;
        
        int i=0;
        while(i<m && target >= matrix[i][0])
        {
            int low = 0;
            int high = n;
            while(low < high)
            {
                int mid = (low+high)/2;
                if(matrix[i][mid] > target)
                    high = mid;
                else if(matrix[i][mid] < target)
                    low = mid+1;
                else
                    return true;
            }
            ++i;
        }
        return false;
    }
    

    '''


Log in to reply
 

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