Home > Software engineering >  Search in a 2D matrix
Search in a 2D matrix

Time:03-19

bool findInMatrix(int x, vector<vector<int>> &arr)
{
    //    Write your code here.
    for(int i = 0;i<arr.size();i  )
    {
        for(int j = 0;j<arr[0].size();j  )
        {
            if(arr[i][j] == x)
                return true;    
        }
    }
    return false;
}

Can anybody help me with this soln, I am able to pass all the testcases but getting TLE!!!

CodePudding user response:

There seems to be a problem in the inner for loop. You are looping over the size of the 0th vector, when you should be looping over the size of ith vector. Each vector can have a different size.

bool findInMatrix(int x, vector<vector<int>> &arr) {

    for(int i = 0; i < arr.size(); i  ) {
        for(int j = 0; j < arr[i].size(); j  ) {
            if(arr[i][j] == x) {
                return true;    
            }
        }
    }
    return false;
}

CodePudding user response:

May be you need to use STL 's find which could be optimal.


#include <iostream>
#include <vector>
#include <algorithm>

using std::vector,std::find;

bool findInMatrix(int x, vector<vector<int>> &arr)
{
    //    Write your code here.     
    for(auto& rows:arr){    
        auto it = find(rows.begin(), rows.end(), x);
        if (it != rows.end())
        {
            return true;
        }   
    }     
    
    return false;
}


int main(){
    
    vector<vector<int>> arr;
    int rows = 5;
    int cols = 4;

    // init with random data
    for(int i = 0; i<rows;i  ){
        vector<int> elems;
         for(int j = 0; j<cols;j  ){            
            elems.push_back(rand()0); 
        }  
        arr.push_back(elems);
    }

    // peek the data
    for(const auto & rows:arr){
        for(const auto &elem:rows ){
            std::cout<<elem<<" ";
        }
        std::cout<<"\n";
    }

    int x = arr[3][2];

    std::cout<<"searching for "<<x<<"\n";
    // search for the element
    std::cout<<findInMatrix(x,arr)<<"\n"; // returns true

    std::cout<<findInMatrix(9999,arr)<<"\n"; // returns false

    return 0;
}


  •  Tags:  
  • c
  • Related