(D&C+Binary search)Divide matrix into 4 parts and discard 2 parts(detailed explanation)


  • 0
    X

    (My English is not good. There are some syntax errors. Several ideas wasn't written, because I don't know how to express them in English. Sorry about that.)
    I will use the matrix in the problem statement as an example.

    Basic idea:

    1. matrix[i][j] > matrix[k][l], where 0 ≤ i ≤ m - 1, 0 ≤ j ≤ n - 1, k ≤ i, j ≤ l, k ≠ i, l ≠ j
    Example:

    1    4    7    11    15
    2    5    8    12    19
    3    6    9    16    22
    10  13   14    17    24
    18  21   23    26    30
    

    Note that number 9 is the largest in the block.

    Example:

    1    4    7    11    15
    2    5    8    12    19
    3    6    9    16    22
    10  13   14    17    24
    18  21   23    26    30
    

    Note that number 30 is the largest in the block.

    2. To Divide matrix into 4 parts, binary search within the "diagonal" a smallest number which is larger than target and is in the bottom-right part. However, if target is in it, directly return true

    The special property of the four parts will be stated soon.

    Example: target = 15
    "diagonal": 1 5 9 17 30

    1    4    7    11    15
    2    5    8    12    19
    3    6    9    16    22
    
    10  13   14    17    24
    18  21   23    26    30
    

    Number 17 is the smallest number which is larger than target in the "diagonal".

    Example: target = 10
    "diagonal": 1 5 9 17

    1    4    7    11    15
    2    5    8    12    19
    3    6    9    16    22
    
    10  13   14    17    24
    

    Number 17 is the smallest number which is larger than target in the "diagonal".

    Example: target = 3
    "diagonal": 1 5 9 17

    1    4    7    11
    
    2    5    8    12
    3    6    9    16
    10  13   14    17
    18  21   23    26
    

    Number 5 is the smallest number which is larger than target in the "diagonal".

    Specially, it is probably that there isn't a smallest number which is larger than target in the "diagonal". This doesn't matter.

    3.Discard the top-left part and bottom-right part, solve the remaining two parts
    Reason:
    All elements in top-left sub-matrix are less than target.
    All elements in bottom-right sub-matrix are larger than target.
    So we needn't to search these two parts

    (Optional)4. If the matrix has only one row or only one column, we directly binary search and return true or false
    5. Combine all sub-problems and return answer

    Time complexity:
    Assume a matrix has N rows and N columns. In every recursion, the matrix is uniformly divided into 4 parts.
    T(N) = 2T(N/4) + logN = N^0.5 + 2logN --> T(N) = O(N^0.5)
    T(N) = 2T(N/2) + logN --> T(N) = O(N)
    What if the matrix isn't uniformly divided into 4 parts, then we must take m into account. In this case, the problem becomes more difficult. I can't solve it.

    Here is my code:

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if (matrix.empty() || matrix[0].empty()) return false;
            return dac(matrix, target, 0, 0, matrix.size() - 1, matrix[0].size() - 1);
        }
    private:
        bool dac(const vector<vector<int>> &matrix, int target,
                 int x0, int y0, int x1, int y1) { // (x0, y0) and (x1, y1) denotes a searching area
            int m = x1 - x0, n = y1 - y0, lo = 0, hi = min(m, n);
            if (m == 0) return rowBS(matrix, target, x0, y0, y1); // If the matrix has only one row (optional)
            if (n == 0) return colBS(matrix, target, y0, x0, x1); // If the matrix has only one column (optional)
            while (lo <= hi) { // binary search the smallest value which is greater than target in the "diagonal"
                int mid = lo + (hi - lo) / 2, x = x0 + mid, y = y0 + mid;
                if      (matrix[x][y] < target) lo = mid + 1;
                else if (matrix[x][y] > target) hi = mid - 1;
                else                            return true;
            }
            if (hi == -1) return false; // The bottom-right sub-matrix is really the current matrix,
                                        // those elements are all greater than target
            return lo <= m && dac(matrix, target, x0 + lo, y0, x1, y0 + lo - 1) // search bottom-left part
                || lo <= n && dac(matrix, target, x0, y0 + lo, x0 + lo - 1, y1); // search top-right part
            // needn't to search the top-left sub-matrix as well as the bottom-right sub-matrix,
            // because all elements in them are either greater than target or smaller than target
        }
        bool rowBS(const vector<vector<int>> &matrix, int target, int x, int lo, int hi) {
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if      (matrix[x][mid] < target) lo = mid + 1;
                else if (matrix[x][mid] > target) hi = mid - 1;
                else                              return true;
            }
            return false;
        }
        bool colBS(const vector<vector<int>> &matrix, int target, int y, int lo, int hi) {
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if      (matrix[mid][y] < target) lo = mid + 1;
                else if (matrix[mid][y] > target) hi = mid - 1;
                else                              return true;
            }
            return false;
        }
    };
    

  • 1

    2T(N/4)

    No, 2T(N/2).


  • -1
    X
    This post is deleted!

  • 1

    So you already forgot your own definition of N? You said "Assume a matrix has N rows and N columns", not "Assume a matrix has N elements".


  • 0
    X

    Oh, it's my fault. Thanks for pointing out.
    So the time complexity is O(n)?


  • 0

    @xpfxzxc No, not O(n), you can't just ignore m.

    Even if you assume that the input is a quadratic matrix, you're creating non-quadratic subproblem matrices, as your last example shows. So your statement "In every recursion, the matrix is uniformly divided into 4 parts" isn't really true, and "T(N) = 2T(N/2)" isn't really valid.

    That said, a proper analysis might indeed show that it's O(N) if the input matrix has size N×N. After all, LeetCode's article looks at the two extremes of this algorithm and ends up with "O(n)" in one and "O(lg n)2" in the other.


Log in to reply
 

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