Learn Algorithm with Leetcode(Ruby):

Intersection of Two Array

Question: Given two arrays, write a function to compute their intersections. Noted, each element in the result should appear as many times as it shows in both arrays, and the result can be in any order.

Examples:

The naive way to solve this problem is to iterate through the first array, and loop through the other array to see if there is any match to the first array, push the value the result array. Sounds pretty straightforward, right?

We can start it by transform the first array to a hash. Each array element will be the key, and the value will be the frequency of each element. For example, in example1, we have num1 and num2, we can make nums1 a hash. It will look like this:

The code for the first step is following:

#set num_hash to an empty hash.
num_hash = {}
#for each element in array nums1, if it appears only once the frequency is 1, else num_hash[num] +=1
nums1.each {|num|
 if num_hash.include?(num)
    num_hash[num] +=1
 else
    num_hash[num] =1
 end
}

The next step is to create an empty array to save the duplicate element when iterating through the second array. Let’s call it result

result = []

Finally, we are going to iterate through the second array to get our result:

nums2.each{|num|
  if num_hash.include?(num) && num_hash[num] > 0
    result << num
    num_hash[num] -= 1
  end
}

At this step, we iterate through the second array to see if it matches num_hash’s key, and we also should make sure the frequency is greater than 0, because we could encounter the situation when the second array has 3 elements that match the key, and the key’s frequency is only 1.

The complete code is as following:

def intersect(nums1, nums2)
  num_hash = {}
  nums1.each {|num|
   if num_hash.include?(num)
     num_hash[num] +=1
   else
     num_hash[num] =1
   end
}
  result = []
  nums2.each{|num|
   if num_hash.include?(num) && num_hash[num] > 0
     result << num
     num_hash[num] -= 1
    end
  result
}
end

And… we finished it!!! Thank you for reading.