# Majority Element

`Array`

Easy

Given an array of sizen, find the majority element. The majority element is the element that appears **more than** `⌊ n/2 ⌋`times.

You may assume that the array is non-empty and the majority element always exist in the array.

**Example 1:**

```
Input:
 [3,2,3]

Output:
 3
```

**Example 2:**

```
Input:
 [2,2,1,1,1,2,2]

Output:
 2
```

## Solution

### Approach 1: HashMap <a href="#approach-2-hashmap" id="approach-2-hashmap"></a>

We can use a HashMap that maps elements to counts in order to count occurrences in linear time by looping over nums. Then, we simply return the key with maximum value.

* Time complexity: O(n)
* Space complexity : O(n)

```java
class Solution {
    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            }
            else {
                counts.put(num, counts.get(num)+1);
            }
        }
        return counts;
    }

    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = countNums(nums);

        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }

        return majorityEntry.getKey();
    }
}
```

### Approach 2: Sorting <a href="#approach-3-sorting" id="approach-3-sorting"></a>

If the elements are sorted in monotonically increasing (or decreasing) order, the majority element can be found at index ⌊ n / 2 ⌋ (and ⌊ n / 2 ⌋ + 1, incidentally, if n is even).

* Time complexity :  O(nlgn)  Sorting the array costs O(nlgn) time in Python and Java, so it dominates the overall runtime.&#x20;
* Space complexity :  O(1) or (O(n))  We sorted nums in place here - if that is not allowed, then we must spend linear additional space on a copy of nums and sort the copy instead.&#x20;

```java
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}
```

### Approach 3: Boyer-Moore Voting Algorithm

> If we had some way of counting instances of the majority element as +1 and instances of any other element as −1, summing them would make it obvious that the majority element is indeed the majority element.

**Complexity Analysis**

* Time complexity :O(n)

  Boyer-Moore performs constant work exactlynntimes, so the algorithm runs in linear time.
* Space complexity :O(1)

  Boyer-Moore allocates only constant additional memory.

```java
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}
```

## Reference

<https://leetcode.com/problems/majority-element/solution/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/array/majority-element.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.