Major element

Answer

Learn more...

Let's define major element as element such that occurs in an array `> n / 2` times

To find it, we'll additionally store two variables: `cadidate` and `count`

Let's go through the array: if `count = 0` then we'll pick current element as a `candidate`

If current element equals to candidate, we'll increase `count` by `1` and else decrease by `1`


So if we are guaranteed that input array contains major element, then it will be certainly found

Thus, we have algorithm `T(n)`, that uses `O(1)` additional space

Else, just do a simple check for candidate


Proof of correctness of that algorithm may be found here