## Friday, May 13, 2016

### Find a common element in all rows of a given row-wise sorted matrix - GeeksforGeeks

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