C# two hashsets O(n) runtime


  • 0
    W

    Pretty descriptive variables so not much explanation needed. I did a little bit of extra work to only later on iterate to check for an intersection on the smaller array, although theoretically there really shouldn't be much runtime difference between the two since each hashset call should be O(1). Runtime should be O(n+m) where n is size of nums1 and m is size of nums2.

    public int[] Intersection(int[] nums1, int[] nums2) {
        var smaller = nums1;
        var larger = nums2;
        if (nums1.Length > nums2.Length) {
            smaller = nums2;
            larger = nums1;
        }
        var hs = new HashSet<int>(larger);
        var intersection = new HashSet<int>();
        foreach(var num in smaller) {
            if(hs.Contains(num)) intersection.Add(num);
        }
        return intersection.ToArray();
    }
    

  • 0
    A

    You dont need to check if one array is smaller or larger than the other. It does not matter whether your first hashset is made from the larger or smaller array. However, using the smaller array might take less space. Although seem to be doing the opposite.


  • 0
    W

    Those were actually my thoughts as well afterwards (hashset of smaller array), so I implemented it in that manner for the second Intersection of Two Arrays problem.


Log in to reply
 

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