Search a 2D Matrix


  • 0

    Approach #1 Brute Force [Accepted]

    Algorithm
    Traverse the array comparing every element with the given target. Return true if the target was found return false after the completion of an iteration meaning that a target is not in a given array.

    C++

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    
        for(int row = 0; row<matrix.size(); row++) {
            for(int col = 0; col<matrix[row].size(); col++) {
              if(matrix[row][col] == target) {
                  return true;
              }
            }
        }
    
        return false;
    }
    

    Complexity Analysis

    • Time complexity : $$O(mn)$$.

    Because each of these nested loops executes m and n times respectively, the total time complexity is $$O(mn)$$, where m represents rows and n columns.

    • Space complexity : $$O(1)$$.

    Approach #2 Binary Search [Accepted]

    Algorithm
    The fact that every row of a given array is sorted make it possible to apply binary search for every row to search for the target value. Keep dividing a row in halves until a finding of the target value.

    C++

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    
        for(int row = 0; row<matrix.size(); row++) {
            int l = 0, r = (int)matrix[row].size()-1;
            while(l<=r) {
                int middle = l + (r - l)/2;
                if(matrix[row][middle] == target) {
                    return true;
                } else if(matrix[row][middle] < target) {
                    l = middle + 1;
                } else {
                    r = middle - 1;
                }
            }
        }
    
        return false;
    }
    

    Complexity Analysis

    • Time complexity : $$O(mlogn)$$.

    Iteration through rows in a given array takes m time where binary search on a row takes logn time, the total time complexity is $$O(mlogn)$$, where m represents rows and n columns.

    • Space complexity : $$O(1)$$.

    Approach #2 Pointer [Accepted]

    Algorithm
    The hint for this approach is the fact that

    Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

    Lets start the pointer at last column of the first row meaning that all numbers below current number are greater than current number and all numbers left to current number are less than current number. Comparing current number with target number it can be decided in which direction to move the pointer. If current number is equal to a target number this means that target value was found stop the pointer. If current number is less than target number then consider numbers below so move the pointer to next row; otherwise, if current number is greater than current number consider all numbers on the left in the same row by moving the pointer to the left.

    Foo

    C++

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

    Complexity Analysis

    • Time complexity : $$O(m+n)$$.

    Iteration through rows in a given array takes m time and iteration through columns takes n time. The fact that the pointer can only move down or left makes the total time complexity $$O(m+n)$$, where m represents rows and n columns.

    • Space complexity : $$O(1)$$.

Log in to reply
 

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