Reduce complexity of a maximum repeated element in an array

Question

I got a list of exercise to do before my exams, they are not graded that's why I did not mark them as homework.

The algorithm take an array of numbers

Given this algorithm:

         Algo-X(A)
                i=1 
                j=1  
                m=0 
                c=0
                while i ≤ |A|
                    if A[i] == A[j]
                        c=c+1 
                    j=j+1
                    if j > |A|
                        if c > m
                           m=c 
                        c=0
                        i=i+1
                        j=i 
                return m

Question 1: Analyze the complexity of Algo-X.

Question 2: Write an algorithm that does exactly the same thing as Algo-X but with a strictly better asymptotic time complexity.

Now, the time complexity of this is O(n^2) right?

The algorithm itself from what I understood search inside an array and return number of the maximum repeated number inside an array.

How can I reduce the complexity?

I can not assume that there is a number that is N/2 times present.

Thanks guys

Can you use a hashmap? In this case, O(n) should be possible. — tobias_k
– tobias_k, Commented Mar 29, 2016 at 14:09
Corrected, thanks! I have to work only with arrays, but even with hash map if all the number are different, (1,2,3,4,5) the complexity will be the same. He asked for a strictly better solution — Zeno Trevisan
– Zeno Trevisan, Commented Mar 29, 2016 at 14:10

Ivan Gritsenko · Accepted Answer · 2016-03-29 14:27:52Z

2

Now, the time complexity of this is O(n^2) right?

Yes, you are right. j will iterate over all elements from i to |A| for every i from 1 to |A|.

∑_{i = 1..|A|}∑_{j = i..|A|}(j) = O(|A|²) = O(n²).

How can I reduce the complexity?

You can first sort the initial array. Then all equal numbers will occur sequentially. You just look for the longest group of equal elements.

sort(A)
m = 1
c = 1
i = 2
while i ≤ |A|
    if A[i] == A[i - 1]
        c = c + 1
    else 
        c = 1
    if c > m
        m = c
    i = i + 1

The time complexity will be O(n * log(n)) for sorting and O(n) for working with sorted array. The total time complexity will be O(n * log(n)).

edited Mar 29, 2016 at 14:27

answered Mar 29, 2016 at 14:18

Ivan Gritsenko

4,2262 gold badges23 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

blazs · Accepted Answer · 2016-03-29 14:23:22Z

2

The problem is easily solvable in linear time and linear space---e.g. by using a hashtable. Here's a pseudocode:

HashTable<Integer, Integer> H = new HashTable<Integer,Integer>();
int res = 0;
for (int i = 0; i < A.length; ++i) {
    if (H.contains(A[i])) { H[A[i]] = 1; }
    else { H[A[i]] += 1; res = Math.max(H[A[i]], res); }
}

return res

It's also solvable in O(n log n) time (and even in O(n) time if the numbers in A are sufficiently similar) and O(1) space by sorting and then scanning the array.

sort(A)
i = j = 0;
res = 0;
while i < |A| do
    j = i+1
    while j < |A| && A[i] == A[j] do
        j = j+1
    done
    res = max(res, j-i+1)
    i = j
done
// Separately handle the case when |A|=1
if |A| = 1 then
    res  = 1
end
return res

Even better, if max difference of elements in A is of order |A|, you can sort A in linear time using counting sort (or some other integer sorting algorithm). Then the algorithm runs in linear time.

edited Mar 29, 2016 at 14:23

answered Mar 29, 2016 at 14:10

blazs

4,85528 silver badges38 bronze badges

2 Comments

Zeno Trevisan Over a year ago

Corrected the algorithm, it was a problem of indentation. It is the first problem, but with has table if all the element are different is not the same complexity?

blazs Over a year ago

If you know that the table contains all distinct elements, then the answer is 1. In this case the problem doesn't make sense.

Collectives™ on Stack Overflow

Reduce complexity of a maximum repeated element in an array

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related