easyHashingPattern: Boyer-Moore Voting
Majority Element Identifier Solution
Problem Statement
Given an array of integers, find and return the integer that appears more than half of the time. If no such integer exists, return -1.
Examples
Example 1:
Input:[2, 2, 1, 1, 1, 2, 2]
Output:2
Explanation: Candidate 2 has more than half of the total votes (4 out of 7 votes)
Example 2:
Input:[3, 3, 3, 1, 1]
Output:3
Explanation: Candidate 3 has more than half of the total votes (3 out of 5 votes)
Constraints
- 1 <= n <= 5 * 10^4
Time: O(N) Space: O(1)
Use Boyer-Moore Voting Algorithm. Maintain a candidate and a count. If count is 0, pick current element as candidate. If same, increment count, else decrement. Time O(N), Space O(1).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.