350. Intersection of Two Arrays II

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

Approach 01:

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()){
            return intersect(nums2, nums1);
        }

        vector<int> result;
        unordered_map<int, int> count;

        for (const int num : nums1){
            ++count[num];
        }

        for (const int num : nums2){

            if (const auto it = count.find(num); it != count.cend() && it->second-- > 0){
                result.push_back(num);
            }
        }

        return result;
    }
};

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) > len(nums2):
            return self.intersect(nums2, nums1)

        result = []
        count = collections.Counter(nums1)

        for num in nums2:
            if count[num] > 0:
                result.append(num)
                count[num] -= 1

        return result

Time Complexity:

• The function checks if nums1 is larger than nums2 and swaps them if necessary. This check is O(1).
• The potential recursive call intersect(nums2, nums1) only happens once, ensuring that nums1 is the smaller or equal-sized array.
• The loop for (const int num : nums1) iterates through nums1 and builds the hash map count. This loop runs in O(m) time, where m is the size of nums1.
• The loop for (const int num : nums2) iterates through nums2 and checks for intersections. This loop runs in O(n) time, where n is the size of nums2.
• Therefore, the overall time complexity is O(m + n).

Space Complexity:

• The hash map count stores at most m key-value pairs (where m is the size of nums1). The space complexity for the hash map is O(m).
• The result vector result stores the intersection elements. In the worst case, this could store all elements of the smaller array (i.e., nums1), which would be O(m).
• Apart from the hash map and result vector, no significant additional space is used.
• Therefore, the overall space complexity is O(m).

Approach 02:

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        ranges::sort(nums1);
        ranges::sort(nums2);

        vector<int> result;
        int i = 0; // nums1's index
        int j = 0; // nums2's index

        while (i < nums1.size() && j < nums2.size())
            if (nums1[i] < nums2[j]) {
                ++i;
            } else if (nums1[i] > nums2[j]) {
                ++j;
            } else {
                result.push_back(nums1[i]);
                ++i;
                ++j;
            }

        return result;
    }
};

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        i = 0  # index for nums1
        j = 0  # index for nums2
        nums1.sort()
        nums2.sort()
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                result.append(nums1[i])
                i += 1
                j += 1

        return result

Time Complexity:

• ranges::sort(nums1) sorts nums1 in O(m \log m) time, where m is the size of nums1.
• ranges::sort(nums2) sorts nums2 in O(n \log n) time, where n is the size of nums2.
• The while loop iterates through both nums1 and nums2 until one of them is exhausted. In the worst case, the loop runs for \min(m, n) iterations.
• Each comparison and potential push back operation inside the loop takes constant time, O(1).
• Therefore, the overall time complexity is O(m \log m + n \log n).

Space Complexity:

• Sorting nums1 and nums2 in place does not require additional space, so the space complexity for sorting is O(1) in terms of auxiliary space.
• The result vector result stores the intersection elements. In the worst case, this could store all elements of the smaller array (i.e., nums1 or nums2), which would be O(\min(m, n)).
• The additional variables i, j, and loop control variables take constant space, O(1).
• Therefore, the overall space complexity is O(\min(m, n)).

Approach 03:

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size())
            return intersect(nums2, nums1);

        vector<int> result;
        int lowerBound = 0; // the lower bound for the binary search

        ranges::sort(nums1);
        ranges::sort(nums2);

        for (const int num : nums1) {
            const int i = binarySearch(nums2, lowerBound, num);
            if (i < nums2.size() && nums2[i] == num) {
                result.push_back(num);
                lowerBound = i + 1;
            }
        }

        return result;
    }

private:
    int binarySearch(vector<int>& nums2, int lo, int target) {
        int l = lo;
        int r = nums2.size();
        while (l < r) {
            const int m = (l + r) / 2;
            if (nums2[m] >= target)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
};

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:

        if len(nums1) > len(nums2):
            return self.intersect(nums2, nums1)

        result = []
        lower_bound = 0  # lower bound for binary search

        # Sort both vectors for binary search
        nums1.sort()
        nums2.sort()

        for num in nums1:
            # Perform binary search on nums2 to find the target element (num)
            i = self.binary_search(nums2, lower_bound, num)
            if i < len(nums2) and nums2[i] == num:
                result.append(num)
                lower_bound = i + 1  # Update lower bound to avoid duplicates

        return result

    def binary_search(self, nums2, l, target):
        r = len(nums2)  # Upper bound (exclusive)
        while l < r:
            m = (l + r) // 2
            if nums2[m] >= target:
                r = m
            else:
                l = m + 1
        return l

Time Complexity:

• ranges::sort(nums1) sorts nums1 in O(m \log m) time, where m is the size of nums1.
• ranges::sort(nums2) sorts nums2 in O(n \log n) time, where n is the size of nums2.
• The for loop iterates through nums1 and performs a binary search for each element. This loop runs in O(m) time, where m is the size of nums1.
• The binary search runs in O(\log n) time for each element in nums1, where n is the size of nums2.
• Therefore, the overall time complexity is O(m \log m + n \log n).

Space Complexity:

• Sorting nums1 and nums2 in place does not require additional space, so the space complexity for sorting is O(1) in terms of auxiliary space.
• The result vector stores the intersection elements. In the worst case, this could store all elements of the smaller array, which would be O(\min(m, n)).
• The additional variables take constant space, O(1).
• Therefore, the overall space complexity is O(\min(m, n)).