## DEV Community is a community of 751,911 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Algorithms: Common Years Problem

I wanted to write about an interesting question I faced in a technical interview:

Given an array of arrays containing birth years and death year of people find out the most common years amongst them.

`````` [[1901,1950],[1930,1960],[1973,2022]]
``````

The steps I use to solve any algorithm problem:

1. Find out how I would do it manually.
2. Write them down as steps.
3. Translate into code.

## 1. Find out how I would do it manually.

The manual way would be to go through each set and remember the range.for ex, the first set is from 1901 to 1950. At the back of our mind, we can remember those years as occurring once, then we go on to the next set. We remember the next set so we can already see the overlap. The first two have been alive together from 1930 to 1950. Then, we move on to the third and last set and we can see that it does not overlap with the other two.

Few things to note. Firstly, we need to connect occurrences to years. Secondly, the years with the most occurrences are the maximum occurences.

## 2. Write them down as steps.

To solve this problem, we need to connect each year with the amount of occurences. Afterwards, we need to find the max occurence and find out all the years that have that.

I decided to use hash to connect`{1901 => 1}`.

## 3. Translate into code.

This is code version of the steps:

``````def findCommonYear(arr)
years = {}
arr.each do |year_set|
start_year = year_set
end_year = year_set
while start_year <= end_year do
puts start_year
if years[start_year]
years[start_year] += 1
else
years[start_year] = 1
end
start_year += 1
end
end
if years.values.max != 1
max_common_count = years.values.max
else
return 0
end
max_common_years = []
years.each do |key,value|
if value == max_common_count
max_common_years << key
end
end
return max_common_years
end

puts findCommonYear([[1910, 1950], [1900, 1951], [1945, 2000]])
``````

## Discussion (4) Nam Hoang Le

Hi Mohammed Shaikh, I want to contribute to your post to make it clearer and reach more reader.
Firstly, about problem description, there is no reason to return `0` if no two arrays overlap each other, just return all possible years. But, maybe we can return `nil` if array input is empty.

Next, let me rewrite your solution with some Ruby features I know:

``````def find_common_year(arr)
return nil if arr.empty?
counter = Hash.new(0)
arr.each do |start_year, end_year|
while start_year <= end_year do
counter[start_year] += 1
start_year += 1
end
end
max_count = counter.values.max
counter.keys.select { |year| counter[year] == max_count }
end
``````

Finally, if we modify problem statement to find only one year among all possible years then there is another solution which has O(n) complexity with `n` is length of array input.

Please tell me if I'm wrong somewhere. Mohammed Shaikh

Hi Nam H. Le,
I wanted to return 0 because there are no years overlapping. That was the original question. As for the modification of the problem statement, I am interested. What would be the problem statement. Let me know what you think 😃 Nam Hoang Le

First of all, to avoid ambiguation, we assume that if a person born (or die), he will born in the first (last) day of that year.
My solution is to create two `2-tuple` for each person: `(start_year, 1)` and `(end_year, -1)`.
And this one has `O(nlogn)` complexity. I'm wrong in previous coment.

``````def find2 arr
ans, max_count, curr_count = nil, 0, 0
arr
.flat_map {|start_year, end_year| [[start_year, 1], [end_year, -1]]}
.sort {|(s1, e1), (s2, e2)| s1 != s2 ? s1 <=> s2 : e2 <=> e1}
.each {|year, delta|
curr_count += delta
ans, max_count = year, curr_count if curr_count > max_count
}
ans
end

find2([[1,5], [5, 9], [2,7]]) #  => 5

# [1      5]
#        [5       9]
#   [2        7]

#           count
# [1, 1]  => 1
# [2, 1]  => 2
# [5, 1]  => 3 : max
# [5,-1]  => 2
# [7, -1] => 1
# [9,-1]  => 0
``````