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 -

Problem statement

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).

Input

We are given an array of unsorted integers.

Output

Return the majority element if exists or return -1

Example

Input :  [1, 1, 1, 2, 2]
Output:  1 
Explanation : 1 occurs 3 times in array of 5 element. Hence majority.
Input : [1,2,1,2]
Output: -1 
Explanation: 1 and 2 occur twice. So no majority.
Input : [1,2,4,7,2,2,2,2]
Output: 2
Explanation: 2 occurs 5 times which is greater than n/2 (n = 9)

Approach 1:

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.

Complexity Analysis

Time:- O(n)

Since we iterate over the array once, the time complexity is O(n).

Space:- 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:

1. Iteration 1: Find the element with max frequency, it has the max potential to have a majority.
2. 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).

Complexity Analysis

Time: O(n)

Since we iterate over the array

Space: O(1)

For extra variable

You can find the code on Github in my Leet Code repo.

Thanks for reading this article, happy coding!!

📝 Save this story in Journal.

👩‍💻 Wake up every Sunday morning to the week’s most noteworthy stories in Tech waiting in your inbox. Read the Noteworthy in Tech newsletter.