Search a 2D Matrix II


  • 0

    Click here to see the full article post


  • 0
    Z

    Another solution.
    class Solution {
    public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size();
    if (m == 0) return false;
    int n = matrix[0].size();
    if (n == 0) return false;
    for (int i = 0; i < m; i++) {
    if (matrix[i][0] > target) return false;
    if (matrix[i][n - 1] < target) continue;
    if (matrix[i][0] == target || matrix[i][n - 1] == target)
    return true;
    int start = 0;
    int end = n - 1;
    int middle = (start + end) / 2;
    while (1) {
    if (start == end || start == middle) {
    if (matrix[i][start] == target || matrix[i][end] == target)
    return true;
    else break;
    }
    if (matrix[i][middle] == target) return true;
    if (matrix[i][middle] > target) {
    end = middle - 1;
    }
    else {
    start = middle + 1;
    }
    middle = (start + end) / 2;
    }
    }
    return false;
    }
    };


  • 0
    J

    The solution which starts searching from the top-left corner:

    class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix.length == 0 || matrix[0].length == 0 || matrix[0][0] > target){
    return false;
    }
    int row = 0;//points horizen elements
    int col = 0;//points vertical elements
    while(row < matrix.length-1){
    if(matrix[row][0] < target){
    row++;
    }else{
    break;
    }
    }
    //get the max row
    while(col <= matrix[0].length-1){
    if(matrix[row][col] < target){
    col++;
    }else{
    break;
    }
    }
    //get the max col
    while(row >= 0 && col < matrix[0].length){
    if(matrix[row][col] == target){
    return true;
    }else if(matrix[row][col] > target){
    row--;
    }else{
    col++;
    }
    }
    return false;
    }
    }


  • 0
    G

    In approach 3, line number 26

    searchRec(left, up, mid-1, down)
    

    Isn't this dividing the matrix into half rather than quarter? So how can we write recurrence relation T(x/4)?

    Thanks!


  • 0

    I think vertical meaning is not correct in the solution. I changed it to following:

    class Solution(object):
        def binary_search(self, matrix, target, start, vertical):
            lo = start
            hi = len(matrix)-1 if vertical else len(matrix[0])-1
    
            while hi >= lo:
                mid = (lo + hi)/2
                if not vertical: # searching a row
                    if matrix[start][mid] < target:
                        lo = mid + 1
                    elif matrix[start][mid] > target:
                        hi = mid - 1
                    else:
                        return True
                else: # searching a column
                    if matrix[mid][start] < target:
                        lo = mid + 1
                    elif matrix[mid][start] > target:
                        hi = mid - 1
                    else:
                        return True
            
            return False
    
        def searchMatrixBS(self, matrix, target):
            # an empty matrix obviously does not contain `target`
            if not matrix:
                return False
    
            for i in range(min(len(matrix), len(matrix[0]))):
                vertical_found = self.binary_search(matrix, target, i, True)
                horizontal_found = self.binary_search(matrix, target, i, False)
                if vertical_found or horizontal_found:
                    return True
            
            return False
    

  • 0
    E

    for Search Space Reduction, for the same reason you can start from top right as well


  • 0
    J

    Another Divide and Conquer. Every time split the matrix into 4 parts. Using binary tree idea search idea in the 2D matrix. The complexity should be O(max(m,n)). Accepted solution as following:

    class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix == null || matrix.length<=0 || matrix[0].length <=0)
    {
    return false;
    }
    return searchSubMatrix(matrix, target, 0, 0, matrix.length, matrix[0].length);
    }

    private boolean searchSubMatrix(int[][] matrix, int target, int startR, int startC, int rows,int columns)
    {
        if(matrix[startR][startC] == target)
        {
            return true;
        }
        
        //the up left is the smallest item and bottom right is the largest one.
        if((columns <= 1 && rows <= 1) 
           || !((matrix[startR+rows-1][startC + columns-1]>= target)&&(matrix[startR][startC]<=target)))
        {
            return false;    
        }
        int newRows = rows/2+rows%2;
        int newColumns = columns/2+columns%2;
        return searchSubMatrix(matrix, target, startR, startC, newRows, newColumns)
            || searchSubMatrix(matrix, target, startR + rows/2, startC, newRows, newColumns)
            || searchSubMatrix(matrix, target, startR + rows/2, startC+columns/2, newRows, newColumns)
            || searchSubMatrix(matrix, target, startR, startC+columns/2, newRows, newColumns);
    }
    

    }


  • 0
    J

    Sorry, the complexity is O(log(max(m,n)))


  • 0
    L

    In Approach 3, Should it be 'searchRec(left, row, mid-1, down)' instead of 'searchRec(left, up, mid-1, down)'?? Otherwise you are recursing the 3/4 area of the original matrix...


  • 0
    M

    Tried solution 4 to count the number of occurrences of a target in a 2D array. I am getting the time limit exceeded error.


  • 0
    M

    But Brute force approach worked. Made slight modification to include counts

    class Solution:
    def searchMatrix(self, matrix, target):
    count = 0
    if len(matrix) == 0 or len(matrix[0]) == 0:
    return 0
    for row in matrix:
    if target in row:
    count+=1
    return count


Log in to reply
 

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