Swift Challenge: Find the majority element [Amazon]

Problem statement

Input

Output

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:

Complexity Analysis

Time:- O(n)

Space:- O(n)

Can we do better?

Boyer-Moore voting Algorithm

  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?

Complexity Analysis

Time: O(n)

Space: O(1)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store