Swift Challenge: Find the majority element [Amazon]

You can read the full story along with many more on The Swift Nerd Blog:

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.

--

--

--

iOS Full stack Engineer @ Booking.com Writer at https://theswiftnerd.com

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

z/VSE Newsflash March 2021

Goodbye Print 👋 Hello Debugger

Python Microservices: API, Object, and Storage Data Models

What is GIT?

Demystifying Closures, Futures and async-await in Rust–Part 3: Async & Await

Day 19 — Roman to Integer

Beginning Swift Programming Part 4 — Decision Making and Loops

What is JavaFX? An Introduction

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
Varun

Varun

iOS Full stack Engineer @ Booking.com Writer at https://theswiftnerd.com

More from Medium

LeetCode #1 Two Sum — Swift solution

Join Our Software Workshops for Polish Dev Community

True or False?

Dependency Injection Patterns