Majority Element

Difficulty: Medium · Topic: Divide & conquer

Given nums where one element appears more than ⌊n/2⌋ times, return it. There's a clean divide-and-conquer solution (the majority of the whole is the majority of one half), and an even simpler Boyer–Moore voting pass in O(1) space.

Examples

majority_element([3,2,3])
→ 3

majority_element([2,2,1,1,1,2,2])
→ 2

Target complexity: time O(n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.