# 20. Majority Element II

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/problems/majority-vote/1)

### ✨ LeetCode Problem of the Day (POTD) Started ✨

* As promised in the poll, I’ve started solving and uploading **LeetCode Problem of the Day (POTD)** solutions! 🎯
* My first solution is now live:\
  [**2516. Take K of Each Character From Left and Right**](https://github.com/Hunterdii/Leetcode-POTD/blob/main/November%202024%20Leetcode%20Solution/2516.Take%20K%20of%20Each%20Character%20From%20Left%20and%20Right.md)

[![LeetCode POTD Solution](https://img.shields.io/badge/LeetCode%20POTD-Solution%20Live-brightgreen?style=for-the-badge\&logo=leetcode) ](https://github.com/Hunterdii/Leetcode-POTD/blob/main/November%202024%20Leetcode%20Solution/2516.Take%20K%20of%20Each%20Character%20From%20Left%20and%20Right.md)[![Solutions Up-to-Date](https://img.shields.io/badge/Solutions-Up%20to%20Date-blue?style=for-the-badge)](https://github.com/Hunterdii/Leetcode-POTD/blob/main/November%202024%20Leetcode%20Solution/2516.Take%20K%20of%20Each%20Character%20From%20Left%20and%20Right.md)[\
Problem DescriptionYou are given an array of integers `arr[]` where each number represents a vote for a candidate. Return the candidates that have votes greater than one-third of the total votes. If there's no majority vote, return an empty array.**Note:** The answer should be returned in an increasing order.Examples:**Input:**\
`arr[] = [2, 1, 5, 5, 5, 5, 6, 6, 6, 6, 6]`\
**Output:**\
`[5, 6]`**Explanation:**\
5 and 6 occur more than `n / 3` times in the array.**Input:**\
`arr[] = [1, 2, 3, 4, 5]`\
**Output:**\
`[]`**Explanation:**\
No candidate occurs more than `n / 3` times.Constraints:`1 <= arr.size() <= 10^6-10^9 <= arr[i] <= 10^9`My Approach**Boyer-Moore Voting Algorithm**:The problem can be efficiently solved using the Boyer-Moore Voting Algorithm to find the top two candidates with the potential to exceed `n / 3` votes.First, identify the two potential majority elements.Then, verify their counts to ensure they actually exceed the threshold.This approach reduces the problem to a linear pass through the array.**Steps:**&#x54;raverse the array to find two majority candidates (`num1` and `num2`) using count variables.Traverse again to count occurrences of the candidates and validate the result.Ensure the final output is sorted to meet the problem requirements.Time and Auxiliary Space Complexity**Expected Time Complexity:** O(n), where `n` is the size of the array. The algorithm requires two linear scans of the array, making it efficient.**Expected Auxiliary Space Complexity:** O(1), as we use only a constant amount of additional space.Code (C)int\* findMajority(int arr\[\], int n, int\* resultSize) {    int num1 = -1, num2 = -1, c1 = 0, c2 = 0;    for (int i = 0; i < n; i++) {        if (arr\[i\] == num1) {            c1++;        } else if (arr\[i\] == num2) {            c2++;        } else if (c1 == 0) {            num1 = arr\[i\];            c1 = 1;        } else if (c2 == 0) {            num2 = arr\[i\];            c2 = 1;        } else {            c1--;            c2--;        }    }    c1 = c2 = 0;    for (int i = 0; i < n; i++) {        if (arr\[i\] == num1) c1++;        else if (arr\[i\] == num2) c2++;    }    int\* result = (int\*)malloc(2 \* sizeof(int));    \*resultSize = 0;    if (c1 > n / 3) result\[(\*resultSize)++\] = num1;    if (c2 > n / 3) result\[(\*resultSize)++\] = num2;    if (\*resultSize == 2 && result\[0\] > result\[1\]) {        int temp = result\[1\];        result\[1\] = result\[0\];        result\[0\] = temp;    }    return result;}Code (Cpp)class Solution {public:    vector\<int> findMajority(vector\<int>& arr) {        int n = arr.size();        int num1 = INT\_MIN, num2 = INT\_MIN;        int c1 = 0, c2 = 0;        for (int x : arr) {            if (x == num1) {                c1++;            } else if (x == num2) {                c2++;            } else if (c1 == 0) {                num1 = x;                c1 = 1;            } else if (c2 == 0) {                num2 = x;                c2 = 1;            } else {                c1--;                c2--;            }        }        c1 = c2 = 0;        for (int x : arr) {            if (x == num1) c1++;            else if (x == num2) c2++;        }        vector\<int> res;        if (c1 > n / 3) res.push\_back(num1);        if (c2 > n / 3) res.push\_back(num2);        sort(res.begin(), res.end());        return res;    \}};Code (Java)class Solution {    public List\<Integer> findMajority(int\[\] nums) {        int num1 = Integer.MIN\_VALUE, num2 = Integer.MIN\_VALUE, c1 = 0, c2 = 0;        int n = nums.length;        for (int x : nums) {            if (x == num1) {                c1++;            } else if (x == num2) {                c2++;            } else if (c1 == 0) {                num1 = x;                c1 = 1;            } else if (c2 == 0) {                num2 = x;                c2 = 1;            } else {                c1--;                c2--;            }        }        c1 = c2 = 0;        for (int x : nums) {            if (x == num1) c1++;            else if (x == num2) c2++;        }        List\<Integer> res = new ArrayList<>();        if (c1 > n / 3) res.add(num1);        if (c2 > n / 3) res.add(num2);        Collections.sort(res);        return res;    \}}Code (Python)class Solution:    def findMajority(self, arr):        num1, num2, c1, c2 = None, None, 0, 0        n = len(arr)        for x in arr:            if x == num1:                c1 += 1            elif x == num2:                c2 += 1            elif c1 == 0:                num1 = x                c1 = 1            elif c2 == 0:                num2 = x                c2 = 1            else:                c1 -= 1                c2 -= 1        c1, c2 = 0, 0        for x in arr:            if x == num1:                c1 += 1            elif x == num2:                c2 += 1        res = \[\]        if c1 > n // 3:            res.append(num1)        if c2 > n // 3:            res.append(num2)        res.sort()        return resContribution and Support](https://github.com/Hunterdii/Leetcode-POTD/blob/main/November%202024%20Leetcode%20Solution/2516.Take%20K%20of%20Each%20Character%20From%20Left%20and%20Right.md)

[For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: ](https://github.com/Hunterdii/Leetcode-POTD/blob/main/November%202024%20Leetcode%20Solution/2516.Take%20K%20of%20Each%20Character%20From%20Left%20and%20Right.md)[Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

***

#### 📍Visitor Count

<div align="center"><img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" alt=""></div>
