## DEV Community is a community of 796,806 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Discussion on: Algorithms: Common Years Problem

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
``````