Find a common element in all rows of a given row-wise sorted matrix - GeeksforGeeks
Given a matrix where every row is sorted in increasing order. Write a function that finds and returns a common element in all rows. If there is no common element, then returns -1.
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
for(int i=0;i<4;i++){
for(int j=0;j<5;j++){
if(hm.containsKey(a[i][j])){
hm.put(a[i][j], (hm.get(a[i][j]))+1);
if(hm.get(a[i][j])==4){
System.out.println(a[i][j]);
return;
}
continue;
}
hm.put(a[i][j], 1);
}
}
Read full article from Find a common element in all rows of a given row-wise sorted matrix - GeeksforGeeks
Given a matrix where every row is sorted in increasing order. Write a function that finds and returns a common element in all rows. If there is no common element, then returns -1.
We can solve this problem in O(mn) time using the approach similar to merge of Merge Sort. The idea is to start from the last column of every row. If elements at all last columns are same, then we found the common element. Otherwise we find the minimum of all last columns. Once we find a minimum element, we know that all other elements in last columns cannot be a common element, so we reduce last column index for all rows except for the row which has minimum value. We keep repeating these steps till either all elements at current last column don’t become same, or a last column index reaches 0.
int findCommon(int mat[M][N]){ // An array to store indexes of current last column int column[M]; int min_row; // To store index of row whose current // last element is minimum // Initialize current last element of all rows int i; for (i=0; i<M; i++) column[i] = N-1; min_row = 0; // Initialize min_row as first row // Keep finding min_row in current last column, till either // all elements of last column become same or we hit first column. while (column[min_row] >= 0) { // Find minimum in current last column for (i=0; i<M; i++) { if (mat[i][column[i]] < mat[min_row][column[min_row]] ) min_row = i; } // eq_count is count of elements equal to minimum in current last // column. int eq_count = 0; // Travers current last column elements again to update it for (i=0; i<M; i++) { // Decrease last column index of a row whose value is more // than minimum. if (mat[i][column[i]] > mat[min_row][column[min_row]]) { if (column[i] == 0) return -1; column[i] -= 1; // Reduce last column index by 1 } else eq_count++; } // If equal count becomes M, return the value if (eq_count == M) return mat[min_row][column[min_row]]; } return -1;}HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
for(int i=0;i<4;i++){
for(int j=0;j<5;j++){
if(hm.containsKey(a[i][j])){
hm.put(a[i][j], (hm.get(a[i][j]))+1);
if(hm.get(a[i][j])==4){
System.out.println(a[i][j]);
return;
}
continue;
}
hm.put(a[i][j], 1);
}
}
Read full article from Find a common element in all rows of a given row-wise sorted matrix - GeeksforGeeks
