Finding majority element in $\mathcal{O}(nlogn)$ time

Question

I am trying to build the logic behind a divide and conquer algorithm that will find the majority element in a matrix $A$ with $n$ elements in $\mathcal{O}(nlogn)$ time.

I thought that in order to make it divide and conquer, I'd need to split the array in two parts. By definition the majority element would be the one that appears in the array at least $\frac{n}{2}$ times. So, naturally, that means that at any time and with any sorting of the array one half of the two will have the overall majority element as its element. Therefore, finding the majority element recursively in either part will lead to my finding the overall.

Let's say that we start with the base of 1 element. So, if the array only has one element then that one is the majority element. But if the array has 2 or more elements, then we devide in two parts, left and right.

Here is where my problem occurs. The major element in either part could be the same, so then it obviously is the one. But if they are different, then how do I choose between the two. I'll give an example if it better explains my problem.

array = [2,2,4,5,1,2,8,2], majority element = 2, count = 4 = 8/2 = length(array)/2

split 1: [2,2,4,5] and [1,2,8,2]

split 2: [2,2] , [4,5], [1,2], [8,2]

split 3 would be the independent elements.

The algorithm will start from left to right, so first we get majority element on the left = 2 with count = 1 and majority element on the right = 2 with count = 1. They are equal so majority element = 2, count = 2.

Then we go to [4] and [5] where clearly each is the majority element of its side. So, how do we choose between those? Like suppose that 5 was instead 2, in which case not choosing 2 which would be the majority element could alter the count which would determine its majority.

Do I have a flaw in my way of thinking? Is this thought process completely wrong? I feel like I'm almost there but have to just determine how I'll choose if the majority elements are not equal.

Answer 1

The idea is to keep track of a "majority candidate" with each recursive call. When trying to merge solutions, if majority candidates are different in each half, you just need to browse the array to check which one appear more than the other. The most frequent will become the new majority candidate.

Let $T(n)$ denote the worst case complexity for an array of length $n$. Given the algorithm, it would verify:

$$T(n) \leqslant 2T\left(\frac{n}{2}\right) + \mathcal{O}(n)$$

The first part corresponds to the recursive calls, and the second part to the verification in case there are different candidates. That would indeed result in time complexity $\mathcal{O}(n\log n)$, but would actually be $\mathcal{O}(n)$ if there is no (or few) cases with multiple candidates.

Note that, as you said, this divide-and-conquer strategy will only work if there is a strict majority, otherwise you could be traped with equality cases. For example, if the array is $[1, 2, 3, 2, 7, 2, 9, 2]$, then each recursive call chosing a candidate among $[1, 2]$, $[3, 2]$, $[7, 2]$ and $[9, 2]$ could pick the wrong one. If there is a strict majority, the real majority element will always be picked at least once.

Also keep in mind that a matrix is just a fancy array.