Time complexity of optimal algorithm for solving this problem

Question

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.

Answer 1

$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.

Answer 2

• 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.