Find majority element (Boyer-Moore)
Medium
Java
Java Arrays
22 views
Problem Statement
Task: assume there is a majority element (> n/2). Return it using O(1) space.
Input Format
An integer n (size of array)
Then n integers
(Assume a majority element exists: appears more than n/2 times)
Then n integers
(Assume a majority element exists: appears more than n/2 times)
Output Format
The majority element.
Example
7 2 2 1 2 3 2 2
2
Constraints
• n ≥ 1
• Majority element always exists
• Use O(1) extra space
• Majority element always exists
• Use O(1) extra space
Concept Explanation
We use Boyer–Moore Voting Algorithm.
Idea:
• Keep a candidate and a count.
• Increase count if same element.
• Decrease count if different.
• When count becomes 0, choose new candidate.
Because majority element appears more than n/2 times,
it will remain as final candidate.
Idea:
• Keep a candidate and a count.
• Increase count if same element.
• Decrease count if different.
• When count becomes 0, choose new candidate.
Because majority element appears more than n/2 times,
it will remain as final candidate.
Step-by-Step Explanation
1.Read n and array.
2.Initialize:
• candidate = 0
• count = 0
3.Loop through each element num:
• If count == 0, set candidate = num.
• If num == candidate, increment count.
• Else decrement count.
4.After loop ends, return candidate.
2.Initialize:
• candidate = 0
• count = 0
3.Loop through each element num:
• If count == 0, set candidate = num.
• If num == candidate, increment count.
• Else decrement count.
4.After loop ends, return candidate.
Concept Explanation
We use Boyer–Moore Voting Algorithm.
Idea:
• Keep a candidate and a count.
• Increase count if same element.
• Decrease count if different.
• When count becomes 0, choose new candidate.
Because majority element appears more than n/2 times,
it will remain as final candidate.
Idea:
• Keep a candidate and a count.
• Increase count if same element.
• Decrease count if different.
• When count becomes 0, choose new candidate.
Because majority element appears more than n/2 times,
it will remain as final candidate.
Step-by-Step Explanation
1.Read n and array.
2.Initialize:
• candidate = 0
• count = 0
3.Loop through each element num:
• If count == 0, set candidate = num.
• If num == candidate, increment count.
• Else decrement count.
4.After loop ends, return candidate.
2.Initialize:
• candidate = 0
• count = 0
3.Loop through each element num:
• If count == 0, set candidate = num.
• If num == candidate, increment count.
• Else decrement count.
4.After loop ends, return candidate.
Input / Output Format
Input Format
An integer n (size of array)
Then n integers
(Assume a majority element exists: appears more than n/2 times)
Then n integers
(Assume a majority element exists: appears more than n/2 times)
Output Format
The majority element.
Constraints
• n ≥ 1
• Majority element always exists
• Use O(1) extra space
• Majority element always exists
• Use O(1) extra space
Examples
Input:
7
2 2 1 2 3 2 2
Output:
2
Example Solution (Public)
static int majority(int[] a){int cand=0,c=0;for(int x:a){if(c==0){cand=x;c=1;}else if(x==cand) c++; else c--; }return cand;}
Official Solution Code
static int majority(int[] a){int cand=0,c=0;for(int x:a){if(c==0){cand=x;c=1;}else if(x==cand) c++; else c--; }return cand;}
Please login to submit solutions.