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

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1's size is small compared to nums2's size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: n = 2
    integer, dimension(n) :: nums1 = [1, 2], nums2 = [2, 2]
    real(kind=DP), dimension(:), allocatable :: intersections
    call get_intersection(nums1, nums2, intersections)
    write (unit=error_unit, fmt='(*(g0))') 'Intersection:', intersections
contains
    subroutine get_intersection(nums1, nums2, intersections)
        implicit none
        integer, dimension(:), intent(in) :: nums1, nums2
        real(kind=DP), dimension(:), allocatable, intent(out) :: intersections
        integer :: i, j, k
        logical :: found

        allocate (intersections(size(nums1)))
        k = 1
        do i = 1, size(nums1)
            found = .false.
            do j = 1, size(nums2)
                if (nums1(i) == nums2(j)) then
                    found = .true.
                    exit
                end if
            end do
            if (found) then
                intersections(k) = nums1(i)
                k = k + 1
            end if
        end do
        intersections = intersections(1:k-1)
    end subroutine get_intersection
end program main
❌ Compiled
❌ Executed
❌ Correct 
module intersection
implicit none
contains

function intersection_array(nums1, nums2) result(intersection)
integer, intent(in) :: nums1(:), nums2(:)
integer :: intersection(size(nums1))

! Sort both arrays
call sort(nums1)
call sort(nums2)

! Initialize intersection array
intersection = 0

! Loop through both arrays and count the number of occurrences of each element
do i = 1, size(nums1)
    do j = 1, size(nums2)
        if (nums1(i) == nums2(j)) then
            intersection(i) = intersection(i) + 1
        end if
    end do
end do

end function intersection_array

end module intersection

program main
use intersection
implicit none
integer, parameter :: nums1(4) = [1, 2, 2, 1], nums2(2) = [2, 2]
integer, parameter :: nums3(4) = [4, 9, 5], nums4(5) = [9, 4, 9, 8, 4]
integer :: intersection(size(nums1))

! Test with example 1
intersection = intersection_array(nums1, nums2)
write (*,*) "Example 1:"
write (*,*) "Input:", nums1, nums2
write (*,*) "Output:", intersection

! Test with example 2
intersection = intersection_array(nums3, nums4)
write (*,*) "Example 2:"
write (*,*) "Input:", nums3, nums4
write (*,*) "Output:", intersection

end program main
🌐 Data from online sources 
def intersect(nums1, nums2):
    count_map = {}
    result = []

    for num in nums1:
        count_map[num] = count_map.get(num, 0) + 1

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

    return result

1. Create a hashmap (or dictionary) to count the occurrences of each integer in the first input array, nums1.
  1. Iterate through the second input array, nums2. a. For each element in nums2, check if the element exists in the hashmap and has a count greater than 0. b. If yes, append the element to the result array and decrement the count in the hashmap for that element.
  2. Return the result array containing the intersection elements.
🌐 Data from online sources 
#include <vector>
#include <unordered_map>

std::vector<int> intersect(std::vector<int>& nums1, std::vector<int>& nums2) {
    std::unordered_map<int, int> count_map;
    std::vector<int> result;

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

    for (int num : nums2) {
        if (count_map[num] > 0) {
            result.push_back(num);
            count_map[num]--;
        }
    }

    return result;
}

1. Create a hashmap (or dictionary) to count the occurrences of each integer in the first input array, nums1.
  1. Iterate through the second input array, nums2. a. For each element in nums2, check if the element exists in the hashmap and has a count greater than 0. b. If yes, append the element to the result array and decrement the count in the hashmap for that element.
  2. Return the result array containing the intersection elements.