Current fastest Ruby implementation, using a hash


  • 0
    J

    I usually don't post my answers but at 64 ms this is currently beating 100% of Ruby submissions.

    # @param {Integer[]} nums1
    # @param {Integer[]} nums2
    # @return {Integer[]}
    def intersect(nums1, nums2)
        nums2Freq = {}
        nums2.each do |n|
            if nums2Freq.include?(n)
                nums2Freq[n] += 1
            else
                nums2Freq[n] = 1
            end
        end
        
        intersection = []
        nums1.each do |n|
            if nums2Freq.include?(n) && nums2Freq[n] > 0
                intersection << n
                nums2Freq[n] -= 1
            end
        end
        
        return intersection
    end
    

    There are some minor optimizations you could do to avoid duplicate hash lookups but the code is clearer without them.


  • 0
    J

    The equivalent Python code does much worse, only beating 18% of others at 88ms.

    class Solution(object):
        def intersect(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: List[int]
            """
            if len(nums1) == 0 or len(nums2) == 0:
                return []
            
            nums2_freq = {}
            for n in nums2:
                if n in nums2_freq:
                    nums2_freq[n] += 1
                else:
                    nums2_freq[n] = 1
            
            intersection = []
            for n in nums1:
                if n in nums2_freq and nums2_freq[n] > 0:
                    intersection.append(n)
                    nums2_freq[n] -= 1
            return intersection
    

    Honestly surprised it performs worse in Python.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.