Migratory Birds Algorithm 🦜🕊️🦅

In this article, I'll be describing how I solved the Migratory Birds Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

If this is your first time reading my data structures and algorithms article, please consider reading more in my Algos in Plain English series.😃

Problem 🎲

Given an array of bird sightings where every element represents a bird type id, determine the id of the most frequently sighted type. If more than 1 type has been spotted with that maximum amount, return the smallest of their ids.

Example

arr = [1, 1, 2, 2, 3]

There are two each of types 1 and 2, and one sighting of type 3. Pick the lower of the two types seen twice: type 1.

Samle Input 0:

Samle Output 0:

Explanation 0:

The different types of birds occur in the following frequencies:

I'll get right into the algorithm. Please feel free to read the full question on HackerRank.

Solution 🔎

Let's consider Sample Input 0 again:

In plain English, we have an array of bird sightings represented by an integer type id. Some birds (id) were sighted more than once, and we need to find the bird that was sighted the most, i.e., the id with the largest occurrence in the array.

Now let's get to the fun part, coding this problem out! 🤓

Step 1️⃣: Get all distinct elements in the array: 🪞

From the problem, it is guaranteed that each type is 1, 2, 3, 4, 5. So we clearly know all distinct elements.

In python, a distinct element is that which has no duplicates. In this case a distinct id will only appear once in the list.

There's a handy set() function in python that creates a set. A set is an unordered collection with no duplicate elements. Sounds like what we need here.

1. Call set() on the array arr to convert it to a sequence of iterable elements with distinct elements.
2. Next we call count() on each of these distinct elements to count the number of occurrences.
3. Finally, we'll store these distinct elements and their respective counts as key, value pairs in a dictionary called count_dict

>>> count_dict = dict((x, arr.count(x)) for x in set(arr))
{1: 1, 3: 1, 4: 3, 5: 1}

As always list comprehension reduces the number of lines of code we have to write, while still preserving code clarity.

Step 2️⃣: Get the key with the maximum value in the dictionary:🔑🔓

Now we've got a dictionary with the key representing the bird type (id) and the value representing the number of occurence, we can easily get the id with the largest count. This is the goal of this problem.

1. We'll use max() to return the largest item in our iterable.
2. To get the key with the largest value in a dictionary dict, we use:

   max(dict, key=dict.get)
   

   In our case, we get:

 >>> max(count_dict, key=count_dict.get)
 4

Step 3️⃣: Putting it all together:

Full code:

def migratoryBirds(arr):
    # Write your code here
    count_dict = dict((x, arr.count(x)) for x in set(arr))

    result = max(count_dict, key=count_dict.get)

    return result


migratoryBirds([1, 4, 4, 4, 5, 3])
>> 4

Hope this article helped with understanding this challenge. Happy Coding!👨🏽‍💻