Given an $N\times N$ matrix $M$ whose elements are integers, find the largest element that occurs in each row of the matrix.
I tried using hashtable as follow:
Idea is to use hash-table(let's call it $ht_1$) to keep track of count of occurrence of each element. Now, To handle case where element repeats in same row we use another hash-table(call this $ht_2$). Now before performing increment in $ht_1$ we check whether this element is already occurred in this row itself or not. If not then and then we perform increment in $ht_1$.
Then once you finish processing whole array as just described make one more pass on array and this time keep track of max element which have exactly $N$ occurrence as noted by $ht_1$.
So overall this runs in $O(N^2)$ expected time.
But Because use of hash-table worst case time complexity is still $O(N^4)$.
Now, I wonder can I do better than this? Means is there any way to solve in $O(N^2)$ in worst case.
Note: There is no other constraint on this.