*Java* an easy-to-understand divide and conquer method


  • 52
    E

    The coding seems to be much more complex than those smart methods such as this one, but the idea behind is actually quite straightforward. Unfortunately, it is not as fast as the smart ones.

    First, we divide the matrix into four quarters as shown below:

      zone 1      zone 2
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
    -----------------------
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
    *  *  *  * | *  *  *  *
      zone 3      zone 4
    

    We then compare the element in the center of the matrix with the target. There are three possibilities:

    • center < target. In this case, we discard zone 1 because all elements in zone 1 are less than target.

    • center > target. In this case, we discard zone 4.

    • center == target. return true.

    For time complexity, if the matrix is a square matrix of size nxn, then for the worst case,

    T(nxn) = 3T(n/2 x n/2)
    

    which makes

    T(nxn) = O(n^log3)
    

    Code in Java:

     public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m<1) return false;
        int n = matrix[0].length;
        
        return searchMatrix(matrix, new int[]{0,0}, new int[]{m-1, n-1}, target);
    }
    
    private boolean searchMatrix(int[][] matrix, int[] upperLeft, int[] lowerRight, int target) {
    	if(upperLeft[0]>lowerRight[0] || upperLeft[1]>lowerRight[1]
    			|| lowerRight[0]>=matrix.length || lowerRight[1]>=matrix[0].length) 
    		return false;
    	if(lowerRight[0]-upperLeft[0]==0 && lowerRight[1]-upperLeft[1]==0)
    		return matrix[upperLeft[0]][upperLeft[1]] == target;
    	int rowMid = (upperLeft[0] + lowerRight[0]) >> 1;
    	int colMid = (upperLeft[1] + lowerRight[1]) >> 1;
    	int diff = matrix[rowMid][colMid] - target;
    	if(diff > 0) {
    		return searchMatrix(matrix, upperLeft, new int[]{rowMid, colMid}, target)
    				|| searchMatrix(matrix, new int[]{upperLeft[0],colMid+1}, new int[]{rowMid, lowerRight[1]}, target)
    				|| searchMatrix(matrix, new int[]{rowMid+1,upperLeft[1]}, new int[]{lowerRight[0], colMid}, target);
    	}
    	else if(diff < 0) {
     		return searchMatrix(matrix, new int[]{upperLeft[0], colMid+1}, new int[]{rowMid, lowerRight[1]}, target)
    				|| searchMatrix(matrix, new int[]{rowMid+1, upperLeft[1]}, new int[]{lowerRight[0], colMid}, target)
    				|| searchMatrix(matrix, new int[]{rowMid+1, colMid+1}, lowerRight, target);
    	}
    	else return true;
    }
    

  • 1
    P

    I came up with the same idea. You can boost the speed by falling back to the brute force searching when your submatrix is small enough. I'm coding in python and found 400 is a good threshold.


  • 8
    L

    A same idea.

    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        if(matrix.length == 1 && matrix[0].length == 1) return matrix[0][0] == target;
        return helper(matrix, target, 0, matrix.length-1, 0, matrix[0].length-1);
    }
    
    public boolean helper(int[][] matrix, int target, int rS, int rE, int cS, int cE) {
        if(rS < 0 || rE >= matrix.length || cS < 0 || cE >= matrix[0].length || rS > rE || cS > cE) return false;
        
        int rM = rS + (rE-rS)/2, cM = cS + (cE-cS)/2;
        
        if(matrix[rM][cM] == target) return true;
        else if(matrix[rM][cM] > target) {
            return helper(matrix, target, rS, rM-1, cS, cM-1) || helper(matrix, target, rS, rM-1, cM, cE) || helper(matrix, target, rM, rE, cS, cM-1);
        } else { // matrix[rM][cM] < target
            return helper(matrix, target, rM+1, rE, cM+1, cE) || helper(matrix, target, rM+1, rE, cS, cM) || helper(matrix, target, rS, rM, cM+1, cE);
        }
    }
    

    }


  • 0
    W

    I like this one better. The one you referred is "smart" but not utilize the D&C, this one does! thumb up!


  • 0
    F

    Is the time complexity for this method optimal? I came up with the same idea, and implemented it in C++. Turned out it exceeded the time limit


  • 0
    S

    What is the Time and Space complexity analysis?


  • 0
    R

    I attempted but the analysis looks a bit involved and not sure what is the correct ans. Essentially we discard m * n / 4 elements and recurse over 3 * (m * n / 4) elements..
    EDIT: I think the time complexity should be O(m*n) ?


  • 0
    X

    very nice idea!


  • 0
    M

    What a piece of work...
    Curious how long does it take to write up.

    Regarding time complexity,
    It reduces the problem by 3/4 every function call. The base case would be a 1 x 1 matrix. So
    mn * (3/4)^x = 1,
    thus we have x = log(3/4, 1/mn) = log(4/3, mn)
    Thus,
    T(m * n) = O(lg(mn)) = O(lg(m) + lg(n))

    So it seems better than O(m+n) to me.


  • 0
    G
    This post is deleted!

  • 0

    @mylemoncake Your analysis is wrong. O(lg(m) + lg(n)) is impossible.


  • 0
    M

    @StefanPochmann could you elaborate?


  • 2

    @mylemoncake You're ignoring the organizational costs. See my explanation here.


  • 0
    M

    @StefanPochmann You are right. Each functional reduce the problem set by 3/4, but also creates 3 more problems.

    So T (MN) = 3 T(1/4 * MN) + 1 = 3 ^X * T(MN/4^X) + X

    When MN/4^X = 1, we have
    X = 3 ^ (log(4, MN)) + log(4, MN)

    Is this correct???
    If yes, how does this reduce to anything that relates to the SO answer and this one, (http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster)


  • 0

    @mylemoncake The "+ X" at the end is too small, but that part is the smaller part anyway, so it doesn't matter for the result. So T(MN) (not X) is indeed O(3log4(MN)). Which is the same as O((MN)log4(3)).


  • 0
    D

    Just share my solution using 2-D binary search searching only 2 regions after every recursive call.
    It searches diagonally. One possible optimization is when the matrix is only one row or one column, just use 1-D BS.

    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int rs = matrix.length;
            if (rs==0) return false;
            int cs = matrix[0].length;
            if (cs==0) return false;
            
            int r1=0, r2=rs;
            int c1=0, c2=cs;
            
            return searchDiagonal(matrix, r1, r2, c1, c2, target);
        }
        
        boolean searchDiagonal(int[][] matrix, int r1, int r2, int c1, int c2, int target) {
            if (r1==r2||c1==c2) return false;
            if (matrix[r2-1][c2-1] == target) return true;
            if (matrix[r2-1][c2-1] < target) return false;
            if (matrix[r1][c1] > target) return false;
            
            
            int d = Math.min(r2-r1, c2-c1);
            int lo=0;
            int hi=d;
            while (lo<hi) {
                int mid = lo + (hi-lo)/2;
                if (matrix[r1+mid][c1+mid] == target) return true;
                else if (matrix[r1+mid][c1+mid] > target) {
                    hi=mid;
                } else {
                    lo=mid+1;
                }
            }
            return searchDiagonal(matrix, r1, r1+lo, c1+lo, c2, target) || searchDiagonal(matrix, r1+lo, r2, c1, c1+lo, target);
        }
        
    }
    

  • 0
    J

    @ElementNotFoundException
    I had the same idea, like many others. Very nice to see someone else take the trouble to post even if it's not the ideal solution in this case. I often gain more insight after studying a second solution to a problem. Plus, it was more fun to solve this way.
    Fwiw, I took the idea from problem 104 - recursion to find max depth of a binary tree. There I did:

    public int MaxDepth(TreeNode root) {
            if(root == null) return 0;
            int left = MaxDepth(root.left);
            int right = MaxDepth(root.right);
            if(left > right) 
                return left + 1;
            return right + 1;
        } 
    

    And here I used the same pattern (don't look close; it's obfuscated by the many variables):

       public bool SearchMatrix(int[,] matrix, int target) {
    
            
    		if (matrix == null || matrix.GetLength(0)*matrix.GetLength(1) == 0)
    			return false;
    			
    		return Helper(matrix, target, 0, matrix.GetLength(0) -1, 0, matrix.GetLength(1) -1); 	
    	        
        }
        
    	
    	public bool Helper(int[,] m, int t, int xbeg, int xend, int ybeg, int yend)
    	{
    		if (xbeg > xend || ybeg > yend)
    			return false;
    			
    		if (xbeg == xend && ybeg == yend)
    			return t == m[xbeg, ybeg];
    			
    		int xmid = (xbeg + xend)/2;
    		
    		int ymid = (ybeg + yend)/2;
    		
    		bool tl = false;
    		bool bl = false;
    		bool tr = false;
    		bool br = false;
    
    //		Console.WriteLine("{0}, {1}, {2}, {3} -- {4}, {5}", xbeg, xend, ybeg, yend, xmid, ymid);		
    		if (m[xmid, ymid] > t) {
    			tl = Helper(m, t, xbeg, xmid-1, ybeg, ymid-1);
                    if (tl) return true;
    			bl = Helper(m, t, xmid, xend, ybeg, ymid-1);
                    if (bl) return true;
    			tr = Helper(m, t, xbeg, xmid-1, ymid, yend);
                    if (tr) return true;
    		}
    		else if (t > m[xmid, ymid]) {
    			br = Helper(m, t, xmid+1, xend, ymid+1, yend);
                    if (br) return true;
    			bl = Helper(m, t, xmid+1, xend, ybeg, ymid);
                    if (bl) return true;
    			tr = Helper(m, t, xbeg, xmid, ymid+1, yend);
                    if (tr) return true;
    		}
    		else 
    			return true;
    		
    //		Console.WriteLine("{0}, {1}, {2}, {3}, {4}, {5}", xbeg, xend, ybeg, yend, xmid, ymid);
    		return tl || bl || tr || br;
    	}
        
    }
    

  • 0
    Y

    @ElementNotFoundException said in *Java* an easy-to-understand divide and conquer method:

    O(n^log3)

    You time complexity is O(n^(1/2*log3)) which is better than O(n). In computer science "log" is default base 2, if it is n^log3, then O(n^log3) is worse than O(n) which is not right.


  • 1
    P

    @yangleizou Be careful about what n is in his post.


  • 0
    Y

    @pei11 Thank you for your reply. He is correct... In my reply, I used n as the total number of elements in the matrix...while in his answer the total number of elements is n^2. So he is right...Thank you again.


Log in to reply
 

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