Swift Challenge: Find the majority element [Amazon]
Find which element wins the vote.
You can read the full story along with many more on The Swift Nerd Blog:
Swift Challenge: Find the majority element -
Asked in : Amazon , Microsift, Visa Our aim to find the majority element from a list of elements. A majority element is…
Our aim to find the majority element from a list of elements. A majority element is that element which occurs more than n/2 times in the array (length = n).
We are given an array of unsorted integers.
Return the majority element if exists or return -1
Input : [1, 1, 1, 2, 2]
Explanation : 1 occurs 3 times in array of 5 element. Hence majority.Input : [1,2,1,2]
Explanation: 1 and 2 occur twice. So no majority.Input : [1,2,4,7,2,2,2,2]
Explanation: 2 occurs 5 times which is greater than n/2 (n = 9)
One way of solving the problem is to iterate the array and maintain a map of the frequency count of every element. We then check for all values in the map and if any exceeds n/2 then we return the element.
Want to read this story later? Save it in Journal.
Since we iterate over the array once, the time complexity is O(n).
We maintain the count of elements and in the worst case, all elements can be distinct. Thus space complexity is also the order of n.
Can we do better?
There can be only one majority element in the array (No other element can occur more than n/2 times if the majority element exists). So we can tweak our approach to find the element with the max frequency since it would have the best chances to become the majority element and later validate the frequency.
Boyer-Moore voting Algorithm
In its simplest form, the algorithm finds a majority element, if there is one: that is, an element that occurs repeatedly for more than half of the elements of the input. However, if there is no majority, the algorithm will not detect that fact, and will still output one of the elements. A version of the algorithm that makes a second pass through the data can be used to verify that the element found in the first pass really is a majority. Source — wiki.
The algorithm is a two-step process:
- Iteration 1: Find the element with max frequency, it has the max potential to have a majority.
- Iteration 2: Validate if the element frequency is more than n/2.
How does it work?
Since the majority element would occur the maximum number of times, even if other elements cancel out the occurrence we would still have some count left. Let's say, you have 10 elements and one element occurs 6times. So then count of the rest elements would be 4. Even if we cancel out the counts for the rest of the elements, we would still have the remaining count of majority element (6-4 = 2 ). We need to validate the frequency because there could be a clash of votes( there are only two elements with equal frequency).
Since we iterate over the array
For extra variable
You can find the code on Github in my Leet Code repo.
Thanks for reading this article, happy coding!!