# Time complexity of optimal algorithm for solving this problem

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.

• Maybe you could use a different data structure that is similar to hash table but has better worst case time complexity? Commented Jan 21, 2020 at 12:08
• Can you suggest such a data structure? Commented Jan 21, 2020 at 14:25
• I can suggest reading the "Data structures" part of Introduction to Algorithms. Commented Jan 21, 2020 at 16:10
• 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. Commented Jan 22, 2020 at 1:42
• But I still wondering about some other solution possible which ensures $O(n^2)$ worst case. Or proof of that no such solution exist. Commented Jan 22, 2020 at 1:44

$$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)$$, especially if you make the hash table say size 3n (which adds only a constant factor). Not guaranteed but likely faster than a O(n^2 log n) array.

• Hash the first row and associate a flag to every element. $$O(n)$$.

• For the next rows,

• Reset all flags $$O(n)$$,

• Scan the row and set the flags of the elements already in the hash $$O(n)$$,

• Delete the elements with a flag reset $$O(n)$$.

In the end, you are left with the values that appear in every row. Total $$O(n^2)$$.

For a simpler version, sort the rows in-place and perform merges of the top row and the next with removal of the elements of the top row not matched.

Worst-case $$O(n^2\log n)$$ guaranteed.

Alternatively, storing the common elements in a balanced tree though still worst-case $$O(n^2\log n)$$, will become faster and faster as the first row empties.