Show problems as
Classic problem #169EasyArrayHash TableDivide and ConquerSortingCountingBoyer–Moore Majority Vote Algorithm

Majority Element

Real-world version: Quorum Drift Value
Tracked in this browser only
Read Majority Element on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A monitoring service asks every node in a cluster for the same figure: how far that node's clock has drifted from the reference, in signed milliseconds. Nodes with a broken sensor answer with whatever number their hardware happens to produce, so the array reports mixes trustworthy answers with junk, in no particular order.

The cluster is provisioned so that the healthy nodes are always a strict majority: one value occupies more than half of the entries of reports. Return that value.

The array is streamed in from the wire, so solve it with a single left-to-right pass over reports and only a constant amount of bookkeeping. Do not sort and do not tally every distinct value.

Examples

Example 1

Input
reports = [4, 7, 4]
Output
4

Two of the three nodes answered 4, which is more than half, so 7 is the faulty reading. Note that the answer is not the entry sitting in the middle.

Example 2

Input
reports = [-6, -6, 2, -6, 9]
Output
-6

Three entries out of five hold -6. Drift can run either side of the reference, so a negative figure is a perfectly ordinary answer.

Constraints

  • n == reports.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= reports[i] <= 10^9
  • The input is provisioned so that some value appears more than n / 2 times

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def quorum_drift(reports: list[int]) -> int:
Java
public int quorumDrift(int[] reports)

More on the same topics