Find two very frequent items in a given array of comparable items

Question

I am new to this community and I have a question regarding a problem I was trying to solve. Could anyone review my algorithm for solving this problem? I want to emphasize also that the algorithm must use the Quickselect algorithm (i.e. https://en.wikipedia.org/wiki/Quickselect).

The question is :

Given an array A[1..n], write an algorithm that checks if there are two elements satisfying the following conditions (Algorithm runtime should be O(n)):

1. $ x < y $
2. The value of x appears more than n/3 times
3. The value of y appears more than n/4 times

The algorithm that I suggest for solving this problem is the following:

1. Find the median of the array A[1..n] using QuickSelect and store its value inside a variable M.
2. Partition the array around M.
3. Find the median of the array A[1...n/2] using QuickSelect (left part of the partitioned array from above) and store its value inside a variable M1.
4. Find the median of the array A[n/2...n] using QuickSelect (right part of the partitioned array from above) and store its value inside a variable M2.
5. Partition the two sub-arrays from stages 3-4 around M1 and M2
6. The elements must satisfy $x,y \in \{M, M1, M2\}$ because the array now is "almost sorted" and the distance between two medians is n/4 (here I am not sure if I can say it is correct because of the pigeonhole principle).
7. Iterate over the array and count the occurrences of M,M1,M2 to check if they're satisfying the conditions of the question then return true if yes, or false otherwise.

EDIT: To be more specific my main concern about this algorithm is in stage 6 where I claim that the elements we are searching for (i.e x,y) must satisfy $x,y \in \{M, M1, M2\}$.
In other words, this is equivalent to the question that if we are given an array A[1..n] and two elements x and y which occurs n/3 times and n/4 times respectively, can we find what those elements are by partitioning the array A[1..n] for the first time around the median of A[1..n] and then partitioning the 2 sub-arrays to the left of the median (A[1..n/2]) and to the right of the median (A[n/2..n]) around their median ?

My motivation behind this claim is the fact that x and y each occur more than n/4 which means that if nor x nor y "sitting" on the median of A[1..n] then the median must be an element such that x<M<y therefore if we split the 2 sub-arrays A[1..n/2] and A[n/2..n] around their medians we can say that their medians must be x and y (because each one of the sub-arrays is of size n/2 and the values x or y occur more than n/4 which is more than half of n/2).
Otherwise, if the median of A[1..n] is x or y (let's say x) then with pretty much similar reasoning we can say that one of the medians of the 2 sub-arrays must be y.

Will appreciate any clue or review for this algorithm, thanks!

Answer 1

Your algorithm is pretty good, although there is ambiguity.

"the median of the array $A[1..n]$" is ambiguous. Is the median of the array $[3,5]$ $3$ or $5$ or $4$?

"the array $A[1..n/2]$" is ambiguous when $n$ is odd.

While it is common to use $n/2$ to denote/mean $n/2$ or $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$, whichever that is suitable on the fly in complexity analysis or in summary understandings, it may lead to off-by-one error in the current case. It is not immediately clear the size of the interior of each interval is no more than $n/4$.

---

Here is a clearer way to express your algorithm.

1. Use QuickSelect to find the $\lfloor n/4\rfloor$-th, $\lfloor n/2\rfloor$-th and $\lfloor 3n/4\rfloor$-th smallest elements of $A$. Let them be $M_1$, $M_2$, $M_3$.
2. For each $i\in\{1,2,3\}$, iterate over the array and count the occurrences of $M_i$. If there are a pair of elements among $M_i$s that satisfy the wanted conditions, return true. Return false otherwise.

---

Here is how we can explain the correctness of the algorithm. Why $x,y \in \{M_1, M_2, M_3\}$?

Assume $n\ge4$ and all $M_i$s as well as the largest element are distinct. The number of elements

• less than $M_1$ is at most $\lfloor n/4\rfloor-1\le n/4$.
• bigger than $M_1$ and smaller than $M_2$ is at most $\lfloor n/2\rfloor-\lfloor n/4\rfloor-1\le n/2-(n/4-1)-1= n/4$.
• bigger than $M_2$ and smaller than $M_3$ is at most $\lfloor 3n/4\rfloor-\lfloor n/2\rfloor-1\le 3n/4-(n/2-1)-1= n/4$.
• bigger than $M_3$ is at most $n-\lfloor 3n/4\rfloor-1\le n-(3n/4-1)-1= n/4 $

So, the number of elements in any group is at most $n/4$. That is still true when $n\lt4$ or some of $M_i$s and the largest element are the same, since there is no element in the relevant groups.

Suppose value $z$ appears more than $n/4$ times. Consider all elements that are the same as $z$. If none of them is $M_i$ for some $i$, then all of them must be contained in one of the groups of elements computed above, which is impossible since the number of elements in any group is at most $n/4$. So $z$ must be one of $M_i$s.
Thanks to the explicit counting above, we can be confident in the logic deduction here.