1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Maybe you could use a different data structure that is similar to hash table but has better worst case time complexity? $\endgroup$ – Laakeri Jan 21 at 12:08
  • $\begingroup$ Can you suggest such a data structure? $\endgroup$ – Vimal Patel Jan 21 at 14:25
  • 1
    $\begingroup$ I can suggest reading the "Data structures" part of Introduction to Algorithms. $\endgroup$ – Laakeri Jan 21 at 16:10
  • $\begingroup$ I found in the section 11.5 of CLR mention about hashing scheme which can provide O(1) time worst case performance if set of keys are static. And in this problem we are just doing hashing once. So I think it would be okay in this case to use it. $\endgroup$ – Vimal Patel Jan 22 at 1:42
  • $\begingroup$ But I still wondering about some other solution possible which ensures $O(n^2)$ worst case. Or proof of that no such solution exist. $\endgroup$ – Vimal Patel Jan 22 at 1:44
3
$\begingroup$

$O(n^2 log n)$ is easy: Create a sorted array of the items in the first row. Lookup the items in the second row in this array using binary search, and remove items that were not present. Same with the third row etc. The last remaining item is the largest one present in evert row. The main effort is $n^2$ lookups in an array of size n.

Using a hash table probably makes it $O (n^2)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.