Sponsored
Sponsored
This approach involves using a hash map (or dictionary) to keep track of the frequencies of elements in one of the arrays, then iterating through the second array to identify common elements, decrementing the frequency count accordingly.
Time Complexity: O(n + m), where n and m are the lengths of nums1 and nums2. Space Complexity: O(min(n, m)) due to the counter.
1#include <stdio.h>
2#include <stdlib.h>
3
4int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
5 int map[1001] = {0};
6 int* result = (int*)malloc(sizeof(int) * (nums1Size + nums2Size));
7 int index = 0;
8 for(int i = 0; i < nums1Size; i++) {
9 map[nums1[i]]++;
10 }
11 for(int i = 0; i < nums2Size; i++) {
12 if(map[nums2[i]] > 0) {
13 result[index++] = nums2[i];
14 map[nums2[i]]--;
15 }
16 }
17 *returnSize = index;
18 return result;
19}In this C implementation, a fixed-size array represents element counts, assuming the constraint (0 <= nums[i] <= 1000) is followed. It decreases counts when a match is found and keeps track of the result size.
Another efficient way is to first sort both arrays and then use two pointers to identify intersections. This approach harnesses the ordered nature post-sort to efficiently match elements by moving through both arrays simultaneously.
Time Complexity: O(n log n + m log m) due to sorting of nums1 and nums2. Space Complexity: O(1) extra space is used, aside from the outputs.
1using System.Collections.Generic;
public class Solution {
public int[] Intersect(int[] nums1, int[] nums2) {
Array.Sort(nums1);
Array.Sort(nums2);
List<int> result = new List<int>();
int i = 0, j = 0;
while (i < nums1.Length && j < nums2.Length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
result.Add(nums1[i]);
i++;
j++;
}
}
return result.ToArray();
}
}Initial sorting sets the stage for comparing nums1 and nums2 with twin indices. Matching elements direct appends to result collection.