:orphan:

Majority Element
================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/majority-element/

Given an array ``nums`` of size ``n``, return *the majority element*.

The majority element is the element that appears more than ``⌊n / 2⌋``
times. You may assume that the majority element always exists in the
array.



**Example 1:**

::

   Input: nums = [3,2,3]
   Output: 3

**Example 2:**

::

   Input: nums = [2,2,1,1,1,2,2]
   Output: 2



**Constraints:**

- ``n == nums.length``
- ``1 <= n <= 5 * 10``\ :sup:```4```
- ``-10``\ :sup:```9```\ ``<= nums[i] <= 10``\ :sup:```9```
- The input is generated such that a majority element will exist in the
  array.



**Follow-up:** Could you solve the problem in linear time and in
``O(1)`` space?

.. highlight:: python

Pattern
-------
Array, Hash Table, Divide and Conquer, Sorting, Counting

Solution
--------
Use a dictionary to count the occurrences of each element in ``nums``. We can
break early once the count of an element exceeds :math:`\\lfloor n/2 \\rfloor`.

Code
----

.. literalinclude:: ../problems/easy/majority-element/majority_element__hash_map.py
    :language: python
    :lines: 11-

Test
----
>>> from majority_element__hash_map import majorityElement
>>> majorityElement([3, 2, 3])
3
>>> majorityElement([2, 2, 1, 1, 1, 2, 2])
2
>>> majorityElement([1])
1

Complexity
----------
| :math:`n` is the length of the input array.
| Time: :math:`O(n)` — single pass with early exit
| Auxiliary Space: :math:`O(n)` — dictionary stores at most :math:`n` key-value pairs

.. autofunction:: majority_element__hash_map.majorityElement