# Majority Element
**Difficulty:** EASY
[External](https://leetcode.com/problems/majority-element)
Canonical: https://scaleengineer.com/dsa/problems/majority-element
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Deloitte](https://scaleengineer.com/companies/deloitte), [Flipkart](https://scaleengineer.com/companies/flipkart), [IBM](https://scaleengineer.com/companies/ibm), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Pwc](https://scaleengineer.com/companies/pwc), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Yandex](https://scaleengineer.com/companies/yandex), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Salesforce](https://scaleengineer.com/companies/salesforce), [Autodesk](https://scaleengineer.com/companies/autodesk), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Swiggy](https://scaleengineer.com/companies/swiggy), [Zenefits](https://scaleengineer.com/companies/zenefits), [Media.net](https://scaleengineer.com/companies/media.net), [CVENT](https://scaleengineer.com/companies/cvent)
---
## Problem
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 * 104`
* `-109 <= nums[i] <= 109`

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

# Approaches
## Brute Force Approach
This approach involves iterating through the array for each element and counting its occurrences. If an element's count exceeds `n/2`, it is returned as the majority element.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** Highly inefficient, with a quadratic time complexity, making it unsuitable for large datasets.
### Explanation
The brute force method uses two nested loops. The outer loop picks an element from the array as a potential candidate for the majority element. The inner loop then iterates through the entire array to count the occurrences of this candidate element.

If the count for any candidate becomes greater than `n/2`, that candidate is the majority element, and we can return it immediately. Since the problem guarantees that a majority element always exists, this process will always find and return the correct element.

```java
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            if (count > n / 2) {
                return nums[i];
            }
        }
        // This part is unreachable given the problem constraints
        // but is needed for the compiler.
        return -1; 
    }
}
```
### Algorithm
1. Get the size of the array, `n`.
2. Use an outer loop to iterate from `i = 0` to `n-1`.
3. Inside the outer loop, select `nums[i]` as the candidate and initialize `count = 0`.
4. Use an inner loop to iterate from `j = 0` to `n-1`.
5. Inside the inner loop, if `nums[j]` is equal to the candidate `nums[i]`, increment `count`.
6. After the inner loop completes, check if `count > n / 2`.
7. If the condition is true, return the candidate `nums[i]`.

## Sorting Approach
By sorting the array, the majority element is guaranteed to be at the middle index (`n/2`). This is because it appears more than `n/2` times, so it will occupy the central position after sorting.
**Time:** O(n log n) · **Space:** O(log n) to O(n)
**Pros:** Very simple to implement using a built-in sort function.
**Cons:** Sorting is slower than linear time approaches.; Modifies the original array.
### Explanation
The intuition behind this approach is that if an element occurs more than `n/2` times in an array, it will always be the middle element when the array is sorted. Let's consider an array of size `n`. If we sort it, the element at index `n/2` (using 0-based indexing) is the median. Since the majority element appears more than `n/2` times, it must occupy this median position.

For example, in `[2,2,1,1,1,2,2]`, `n=7`. `n/2` is 3. After sorting, we get `[1,1,1,2,2,2,2]`. The element at index 3 is `2`, which is the majority element.

```java
import java.util.Arrays;

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}
```
### Algorithm
1. Sort the input array `nums` in non-decreasing order.
2. The majority element is guaranteed to be at the index `n/2`.
3. Return the element `nums[n/2]`.

## Hash Map Approach
This approach uses a hash map to store the frequency of each element. We iterate through the array once to build the frequency map and then find the element with a count greater than `n/2`.
**Time:** O(n) · **Space:** O(n)
**Pros:** Achieves linear time complexity, which is efficient for large arrays.
**Cons:** Requires extra space proportional to the number of unique elements, which can be up to O(n).
### Explanation
We can find the majority element by counting the occurrences of each element in the array. A hash map is an ideal data structure for this task, as it provides average O(1) time complexity for insertions and lookups.

We traverse the input array `nums`. For each element, we update its count in the hash map. If the element is not yet in the map, we add it with a count of 1. If it's already present, we increment its count.

After populating the map, we can iterate through its entries to find which element has a count greater than `n/2`. Since a majority element is guaranteed to exist, we will surely find one.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        int n = nums.length;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > n / 2) {
                return entry.getKey();
            }
        }
        
        // Unreachable code given problem constraints
        return -1;
    }
}
```
### Algorithm
1. Create a `HashMap` to store elements as keys and their frequencies as values.
2. Iterate through the input array `nums`.
3. For each `num`, update its frequency in the hash map.
4. After the first loop, iterate through the entries of the hash map.
5. For each entry, check if its value (frequency) is greater than `n/2`.
6. If it is, return the key corresponding to that entry.

## Boyer-Moore Voting Algorithm
This is an optimal algorithm that finds the majority element in linear time and constant space. It works by maintaining a candidate and a counter, incrementing for the candidate and decrementing for other elements. The majority element's count will prevail.
**Time:** O(n) · **Space:** O(1)
**Pros:** Most efficient solution with linear time and constant space.; Solves the follow-up problem directly.
**Cons:** Can be less intuitive to understand compared to more straightforward approaches like using a hash map or sorting.
### Explanation
The Boyer-Moore Voting Algorithm is a clever and efficient method for finding the majority element. The core idea is based on the fact that the majority element occurs more than `n/2` times. This means it appears more often than all other elements combined.

The algorithm maintains two variables: a `candidate` for the majority element and a `count`. We iterate through the array.
- If `count` is 0, we choose the current element as the new `candidate`.
- If the current element is the same as the `candidate`, we increment `count`.
- If the current element is different, we decrement `count`.

Essentially, we are pairing up each occurrence of the majority element with an occurrence of a non-majority element. Since the majority element is more frequent, it will be the last one standing as the `candidate`.

Because the problem guarantees that a majority element always exists, the final `candidate` will be the answer. If there was no guarantee, a second pass would be needed to verify if the candidate's count is actually greater than `n/2`.

```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;
    }
}
```
### Algorithm
1. Initialize `count = 0` and `candidate = null`.
2. Iterate through each element `num` in the array `nums`.
3. If `count` is 0, set `candidate = num`.
4. If `num` is equal to `candidate`, increment `count`. Otherwise, decrement `count`.
5. After the loop finishes, `candidate` will hold the majority element. Return `candidate`.

# Solutions
### CSharp

```csharp
public class Solution { public int MajorityElement ( int [] nums ) { int cnt = 0 , m = 0 ; foreach ( int x in nums ) { if ( cnt == 0 ) { m = x ; cnt = 1 ; } else { cnt += m == x ? 1 : - 1 ; } } return m ; } }
```

### Java

```java
class Solution { public int majorityElement ( int [] nums ) { int cnt = 0 , m = 0 ; for ( int x : nums ) { if ( cnt == 0 ) { m = x ; cnt = 1 ; } else { cnt += m == x ? 1 : - 1 ; } } return m ; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var majorityElement =
  function (nums) {
    let cnt = 0;
    let m = 0;
    for (const x of nums) {
      if (cnt === 0) {
        m = x;
        cnt = 1;
      } else {
        cnt += m === x ? 1 : -1;
      }
    }
    return m;
  };

```

### Python

```python
class Solution:
    def majorityElement(self, nums: List[int]) -> int: cnt = m = 0 for x in nums: if cnt == 0: m, cnt = x, 1 else: cnt += 1 if m == x else - 1 return m

```

### CPP

```cpp
class Solution { public: int majorityElement ( vector < int >& nums ) { int cnt = 0 , m = 0 ; for ( int & x : nums ) { if ( cnt == 0 ) { m = x ; cnt = 1 ; } else { cnt += m == x ? 1 : - 1 ; } } return m ; } };
```