Given a sorted row and column matrix, find if it contains an element?
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
/*
1 2 3 4
6 7 8 9
11 12 13 14
16 17 18 19
1 2 3 4
6 7 8 9
11 12 13 14
16 17 18 19
We cut the matrix into 4 blocks at the center. We check the center element. If that is the element we are looking for, we return true else we do the same recursively in those 4 divided blocks. If the number is less than the top left most element in the block and greater than the right bottom most element in the block, we can return false since the element doesn't belong to the block.
*/
//My implementation
bool findElement(int ** nos, int r1, int c1, int r2, int c2, int no ){
if(r1 > r2 ||c1 > c2) return false;
if(no < nos[r1][c1] || no > nos[r2][c2]) return false;
int mid_r = (r1+r2)/2;
int mid_c = (c1+c2)/2;
if(nos[mid_r][mid_c] == no) return true;
return findElement(nos, r1, c1, mid_r, mid_c, no) ||
findElement(nos, r1, mid_c+1, mid_r, c2, no) ||
findElement(nos, mid_r+1, c1, r2, mid_c, no) ||
findElement(nos, mid_r, mid_c+1, r2, c2, no);
}
void sortRows(int ** nos, int row_size, int col_size){
for(int i=0;i<row_size;i++){
sort(nos[i], nos[i] + col_size);
}
}
void sortCols(int ** nos, int row_size, int col_size){
vector<int> list;
for(int i=0;i<col_size;i++){
for(int j=0;j<row_size;j++){
list.push_back(nos[j][i]);
}
sort(list.begin(), list.end());
for(int j=0;j<row_size;j++){
nos[j][i] = list[j];
}
list.clear();
}
}
class Array{
public:
int ** arr;
int row_size;
int col_size;
};
Array getARandomArray(int size_cap){
int row_size = rand()%size_cap + 1;
int col_size = rand()%size_cap + 1;
int ** nos = new int*[row_size];
for(int i=0;i<row_size;i++){
nos[i] = new int[col_size];
}
Array toreturn;
toreturn.arr = nos;
toreturn.row_size = row_size;
toreturn.col_size = col_size;
return toreturn;
}
int main()
{
int value_range = 5000000; //Value range of elements in the matrix
int total_tests = 100000; // Total tests to be performed
int array_size_cap = 1000; // The generated array will have 1 <= row, col <= 1000
for(int t=0;t<total_tests;t++){
Array tempa = getARandomArray(array_size_cap);
int ** nos = tempa.arr;
int row_size = tempa.row_size;
int col_size = tempa.col_size;
//Assign random values in value range
for(int i=0;i<row_size;i++){
for(int j=0;j<col_size;j++){
nos[i][j] = rand()%value_range;
}
}
//pick a random element at random spot in the array
int rand_item_row = rand() % row_size;
int rand_item_col = rand() % col_size;
//sort the array row and column wise
sortRows(nos, row_size, col_size);
sortCols(nos, row_size, col_size);
//check if the algorithm finds that element
assert(findElement(nos, 0, 0, row_size-1, col_size-1, nos[rand_item_row][rand_item_col]) == true);
// free dynamically allocated memory
for( int i = 0 ; i < row_size ; i++ )
{
delete[] nos[i]; // delete array within matrix
}
// delete actual matrix
delete[] nos;
}
cout << "All tests passed ... " << endl;
return 0;
}
