LeetCode //C - 350. Intersection of Two Arrays II

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

From: LeetCode
Link: 350. Intersection of Two Arrays II

Solution:

Ideas:

1. Counting Frequencies: We first create two arrays (count1 and count2) of size 1001, initialized to 0. These arrays will store the frequency of each number from nums1 and nums2, respectively.
2. Finding the Intersection: For each number from 0 to 1000, we calculate the minimum count from both arrays. This minimum count gives the number of times this number will appear in the result.
3. Storing the Result: We store the intersection in a dynamically allocated array, keeping track of the number of elements added with the index variable.
4. Returning the Result: Finally, we set the value of returnSize to the number of elements in the result and return the result array.

Code:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int count1[1001] = {0};
    int count2[1001] = {0};
    
    // Count occurrences of each element in nums1
    for (int i = 0; i < nums1Size; i++) {
        count1[nums1[i]]++;
    }
    
    // Count occurrences of each element in nums2
    for (int i = 0; i < nums2Size; i++) {
        count2[nums2[i]]++;
    }
    
    // Find the intersection
    int* result = (int*)malloc(sizeof(int) * (nums1Size < nums2Size ? nums1Size : nums2Size));
    int index = 0;
    
    for (int i = 0; i <= 1000; i++) {
        int minCount = (count1[i] < count2[i]) ? count1[i] : count2[i];
        while (minCount > 0) {
            result[index++] = i;
            minCount--;
        }
    }
    
    *returnSize = index;
    return result;
}