3. Majority Element[Amazon]

3. Majority Element[Amazon]

Given an array of size n, find the majority element. The majority element is the element that appears more than floor(n/2) times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example :

Input : [2, 1, 2]
Return  : 2 which occurs 2 times which is greater than 3/2.

To solve this problem, developers need to understand few concepts:

1. Sorting : If the elements are sorted in monotonically increasing (or decreasing) order, the majority element can be found at index

Complexity Analysis

• Time complexity : O(nlogn)
• Space complexity : O(1)

2. Hash-map : We can use a HashMap that maps elements to counts in order to count occurrences in linear time by looping over A array. Then, we simply return the key with maximum value.

Complexity Analysis

• Time complexity : O(n)
• Space complexity : O(n)

3. Boyer–Moore majority vote algorithm

Complexity Analysis

• Time complexity : O(n)
• Space complexity : O(1)

Problem: Majority Element

How to Approach this problem?

• Sorting solution
• Hash-map solution
• Boyer-Moore solution

We will see the Boyer-Moore solution in this article, as its highly optimised solution.

To test the solution:

let input = [2, 1, 2]
let result = majorityElement(input)

Congratulations! You just solved a problem that was asked in interviews at Microsoft , Yahoo , Google and Amazon .

Thanks for reading this article, keep learning & growing.

Github: https://github.com/charlieInDen/InterviewQuestions-Swift/