The Boyer-Moore Majority Voting Algorithm is a well-known and efficient algorithm used to find the majority element in an array, i.e., an element that appears more than n/2 times. This algorithm, initially designed by Robert S. Boyer and J Strother Moore in 1981, is widely used in various applications, including data analysis and stream processing. However, in some scenarios, we may need to find elements that occur more than n/k times, where k is a positive integer. In this article, we explore the generalization of the Boyer-Moore Majority Voting Algorithm to solve this problem efficiently.
Understanding Boyer-Moore Majority Voting Algorithm:
Before we dive into the generalization of the algorithm, let’s briefly review how the original Boyer-Moore Majority Voting Algorithm works.
1. Initialization: We start by initializing two variables, “candidate” and “count,” to null and 0, respectively.
2. Majority Element Detection: We iterate through the array and update the “candidate” and “count” variables as follows:
- If “count” is 0, we set the current element as the “candidate.”
- If the current element is equal to the “candidate,” we increment “count” by 1.
- If the current element is different from the “candidate,” we decrement “count” by 1.
3. Verification: After the iteration, the “candidate” variable stores a potential majority element. We then perform a second pass to verify if the “candidate” indeed appears more than n/2 times in the array.
Time Complexity: O(N).
Auxiliary Space: O(1).
If you want to know more about Boyer-Moore Majority Voting Algorithm you can click here.
Generalizing for n/k Occurrences:
The Boyer-Moore Majority Voting Algorithm is a powerful tool for finding the majority element in an array, i.e., an element that appears more than n/2 times, where n is the size of the array. But what if we need to find elements that occur more than n/k times, where k is any positive integer? In this article, we’ll make this algorithm more accessible and show you how to adapt it for this general scenario.
Understanding the Modified Algorithm
To extend the Boyer-Moore Majority Voting Algorithm to find elements that appear more than n/k times, we’ll need to make a few tweaks. Here’s a simplified version:
1. Initialization: Start by creating an array with k-1 slots, each storing a pair of values (element, count) to represent potential candidates and their counts. Additionally, keep two variables, count_others and count_cleared, both initially set to 0.
2. Scanning the Array: Traverse through the array, and for each element, follow these steps:
- If the element already exists in one of the k-1 slots, increment its count.
- If there’s an empty slot in the array, insert the current element as a new candidate with a count of 1.
- If neither of the above conditions applies, decrease the count of all candidates by 1.
3. Verification: After this step, you’ll have k-1 candidates along with their counts. To identify the elements occurring more than n/k times, iterate through the array once more. For each candidate, check if its actual count is greater than n/k. Additionally, keep track of elements cleared from the candidates during the scanning step using the count_cleared variable.
Below is the implementation of the above idea:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;vector<int> majorityElement(vector<int>& nums, int k){ int n = nums.size(); // Initialize an array of pairs to store k-1 // candidates and their counts vector<pair<int, int> > candidates(k - 1); // Initialize candidate elements // and their counts to 0 for (int i = 0; i < k - 1; i++) { candidates[i] = { 0, 0 }; } // Step 1: Scanning the Array for (int num : nums) { bool found = false; for (int j = 0; j < k - 1; j++) { // If the element exists in // candidates if (candidates[j].first == num) { // Increment its count candidates[j].second++; found = true; break; } } // If the element is not in candidates if (!found) { for (int j = 0; j < k - 1; j++) { // Find an empty slot if (candidates[j].second == 0) { // Insert as a new candidate candidates[j] = { num, 1 }; found = true; break; } } } // If all slots are occupied if (!found) { // Decrement counts // of all candidates for (int j = 0; j < k - 1; j++) { candidates[j].second--; } } } // Initialize a vector to store // the final results vector<int> ans; // Step 2: Verification for (int i = 0; i < k - 1; i++) { int count = 0; for (int j = 0; j < n; j++) { if (nums[j] == candidates[i].first) { count++; } } // If the count is greater than n/k if (count > n / k) { // Add the candidate // to the result ans.push_back(candidates[i].first); } } return ans;}// Drivers codeint main(){ vector<int> nums = { 3, 2, 3 }; int k = 3; vector<int> result = majorityElement(nums, k); cout << "Elements occurring more than " << nums.size() / k << " times: "; for (int num : result) { cout << num << " "; } cout << endl; return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class MajorityElement { public List<Integer> majorityElement(int[] nums, int k) { int n = nums.length; int[][] candidates = new int[k - 1][2]; for (int i = 0; i < k - 1; i++) { candidates[i] = new int[]{0, 0}; } for (int num : nums) { boolean found = false; for (int j = 0; j < k - 1; j++) { if (candidates[j][0] == num) { candidates[j][1]++; found = true; break; } } if (!found) { for (int j = 0; j < k - 1; j++) { if (candidates[j][1] == 0) { candidates[j][0] = num; candidates[j][1] = 1; found = true; break; } } } if (!found) { for (int j = 0; j < k - 1; j++) { candidates[j][1]--; } } } List<Integer> ans = new ArrayList<>(); for (int[] candidate : candidates) { int count = 0; for (int num : nums) { if (num == candidate[0]) { count++; } } if (count > n / k) { ans.add(candidate[0]); } } return ans; }} |
Python
def majority_element(nums, k): n = len(nums) candidates = [None] * (k-1) # Initialize an array to store k-1 candidates # Initialize candidate elements and their counts to 0 for i in range(k-1): candidates[i] = [0, 0] # Step 1: Scanning the Array for num in nums: found = False for j in range(k-1): if candidates[j][0] == num: # If the element exists in candidates candidates[j][1] += 1 # Increment its count found = True break if not found: # If the element is not in candidates for j in range(k-1): if candidates[j][1] == 0: # Find an empty slot candidates[j] = [num, 1] # Insert as a new candidate found = True break if not found: # If all slots are occupied for j in range(k-1): candidates[j][1] -= 1 # Decrement counts of all candidates ans = [] # Initialize a list to store the final results # Step 2: Verification for candidate in candidates: count = nums.count(candidate[0]) # Count actual occurrences of each candidate if count > n // k: # If the count is greater than n/k ans.append(candidate[0]) # Add the candidate to the result return ans |
C#
using System;using System.Collections.Generic;using System.Linq;class Program { static List<int> MajorityElement(List<int> nums, int k) { int n = nums.Count; // Initialize an array of tuples to store k-1 // candidates and their counts var candidates = new List<Tuple<int, int> >(k - 1); // Initialize candidate elements and their counts to // 0 for (int i = 0; i < k - 1; i++) { candidates.Add(new Tuple<int, int>(0, 0)); } // Step 1: Scanning the Array foreach(int num in nums) { bool found = false; for (int j = 0; j < k - 1; j++) { // If the element exists in candidates if (candidates[j].Item1 == num) { // Increment its count candidates[j] = Tuple.Create( candidates[j].Item1, candidates[j].Item2 + 1); found = true; break; } } // If the element is not in candidates if (!found) { for (int j = 0; j < k - 1; j++) { // Find an empty slot if (candidates[j].Item2 == 0) { // Insert as a new candidate candidates[j] = Tuple.Create(num, 1); found = true; break; } } } // If all slots are occupied if (!found) { // Decrement counts of all candidates for (int j = 0; j < k - 1; j++) { candidates[j] = Tuple.Create( candidates[j].Item1, candidates[j].Item2 - 1); } } } // Initialize a list to store the final results List<int> ans = new List<int>(); // Step 2: Verification for (int i = 0; i < k - 1; i++) { int count = 0; foreach(int num in nums) { if (num == candidates[i].Item1) { count++; } } // If the count is greater than n/k if (count > n / k) { // Add the candidate to the result ans.Add(candidates[i].Item1); } } return ans; } static void Main(string[] args) { List<int> nums = new List<int>{ 3, 2, 3 }; int k = 3; List<int> result = MajorityElement(nums, k); Console.Write("Elements occurring more than " + nums.Count / k + " times: "); foreach(int num in result) { Console.Write(num + " "); } Console.WriteLine(); }} |
Javascript
function majorityElement(nums, k) { const n = nums.length; const candidates = new Array(k - 1); for (let i = 0; i < k - 1; i++) { candidates[i] = [0, 0]; } for (const num of nums) { let found = false; for (let j = 0; j < k - 1; j++) { if (candidates[j][0] === num) { candidates[j][1]++; found = true; break; } } if (!found) { for (let j = 0; j < k - 1; j++) { if (candidates[j][1] === 0) { candidates[j] = [num, 1]; found = true; break; } } } if (!found) { for (let j = 0; j < k - 1; j++) { candidates[j][1]--; } } } |
Elements occurring more than 1 times: 3
Time Complexity: O(n*k)
Auxiliary Space: O(k)
Conclusion:
In summary, the Boyer-Moore Majority Voting Algorithm, originally designed to find the majority element in an array, can be adapted to detect elements that appear more than n/k times efficiently. By modifying the initialization, scanning, and verification steps as outlined above, you can apply this generalized algorithm in various situations where you need to find elements with specific frequency requirements. This versatile algorithm is a valuable tool for data analysis, stream processing, and many other applications where efficient majority element detection is essential.
