Majority Element-II

Hard

Boyer-Moore with two candidates

Problem

Given an integer array nums of size n. Return all elements which appear more than n/3 times in the array. The output can be returned in any order.

In simple words

At most two values can appear more than a third of the time — track two candidates (extended Boyer-Moore).

The idea

At most two values can appear more than n/3 times, so run the vote-cancelling algorithm with two candidates and two counters. Because the algorithm can produce false positives, a verification pass counting the two candidates is mandatory.

The trick

At most two answers exist — that bound is why two candidates suffice.
Always verify with a second pass; cancellation alone does not prove a majority.
Check the candidate matches before touching either counter.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(n)spaceO(1)

1c1 = c2 = null; n1 = n2 = 02for x in nums:3  if x == c1: n1++4  elif x == c2: n2++5  elif n1 == 0: c1 = x; n1 = 16  elif n2 == 0: c2 = x; n2 = 17  else: n1--; n2--8// re-count c1, c2 and keep those appearing > n/3 times

Input

array: [1, 2, 1, 1, 3, 2]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [3, 2, 3]
Output:: [3]
Explanation:: Only 3 appears more than n/3 times.

Example 2

Input:: nums = [1, 1, 1, 3, 3, 2, 2, 2]
Output:: [1, 2]
Explanation:: Both 1 and 2 pass the n/3 bar.

Example 3

Input:: nums = [1, 2, 3]
Output:: []
Explanation:: No value beats n/3 here.

Constraints

n == nums.length.
2 <= n <= 10^5
-10^4 <= nums[i] <= 10^4

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.