My code is short, but...is it the best efficient?


  • 1
    C
    bool searchMatrix(vector<vector<int> > &matrix, int target) 
    {
        vector<int> v;
        for (int i = 0; i < matrix.size(); ++i)
            for (int j = 0; j < matrix[i].size(); ++j)
                v.push_back(matrix[i][j]);
        
        return binary_search(v.begin(), v.end(), target);
    }
    

    I think this proble has a better solution, but this code is so pretty....


  • 0
    C

    Could you solve this problem without extra space ?


  • 0
    S

    What do you think about the time complexity of this solution? And, do you really think it is fine to use binary_search in a real interview?


  • 0
    C

    O(n*m) . Sure, you can use std:binary_search and std:upper_bound in the interview, and if the interviewer ask you implement those functions , implement it. It is still better than write 20-30 lines code in a big function, in my opinion.


  • 6
    W

    No, this is worse than a linear search, since you have to go through every element.
    You can do it faster by implementing binary search directly on the matrix.


  • 0
    R

    while you traversal you can get the answer, but it's not a good solution.
    for (int i = 0; i < matrix.size(); ++i)
    for (int j = 0; j < matrix[i].size(); ++j)
    if (matrix[i][j] == target) return true;
    return false;


  • 0
    A

    As you are already go through every entry of matrix why are you even bother to push it into some other array simply check if that element is present or not.


Log in to reply
 

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