Find an element appearing more than times in , or report none exists. Observation: If a majority exists, it's either:
- The median (quantile query)
- Or we can verify a candidate in
Algorithm:
Find median using kthSmallest
Count its frequency
If frequency , return it
Otherwise, no majority exists.
Time: for single query. This works because the majority element, if it exists, must be the median.