DEV Community

Discussion on: Algorithms: Common Years Problem

Collapse
namhle profile image
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.

Collapse
mqshaikh8 profile image
Mohammed Shaikh Author

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 😃

Collapse
namhle profile image
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
Thread Thread
mqshaikh8 profile image
Mohammed Shaikh Author

Thanks Nam H. Le. That is an interesting variation of the problem