Major element


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 `cadidate`

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