Application: Range Majority

Find an element appearing more than $(r - l + 1) / 2$ times in $A[l..r]$, or report none exists. Observation: If a majority exists, it's either:

• The median (quantile query)
• Or we can verify a candidate in $O(\log \sigma)$

Algorithm:

$1.$ Find median using kthSmallest

$2.$ Count its frequency

$3.$ If frequency $> (r - l + 1) / 2$, return it

$4.$ Otherwise, no majority exists.

Time: $O(\log \sigma)$ for single query. This works because the majority element, if it exists, must be the median.