Common Element Frequencies — Problem Statement & Solution Guide
Problem Description
Given two arrays of integers arr1 and arr2, find the common elements between them, preserving the minimum frequency of each common element. Return the resulting array of common elements.
Examples
Input
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5], [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
Output
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
Explanation: Step-by-step: with input [1, 1, 2, 2, 3, 3, 4, 4, 5, 5] and [1, 1, 2, 2, 3, 3, 4, 4, 5, 5], we find the common elements between them, preserving the minimum frequency of each common element. Since both arrays have the same elements with the same frequency, the resulting array will be the same as the input arrays.
Input
[1, 2, 2, 3, 3, 3], [2, 2, 3, 3, 4, 4]
Output
[2, 2, 3, 3]
Explanation: Step-by-step: with input [1, 2, 2, 3, 3, 3] and [2, 2, 3, 3, 4, 4], we find the common elements between them, preserving the minimum frequency of each common element. The common elements are 2 and 3. The minimum frequency of 2 is 2 and the minimum frequency of 3 is 2. Therefore, the resulting array will be [2, 2, 3, 3].
Constraints
- 1 <= arr1.length, arr2.length <= 1000
- 0 <= arr[i] <= 1000
Optimal Approach & Strategy
Create frequency map of arr1. Iterate arr2: if element in map and freq > 0, add to result and decrement freq. Time O(N+M), Space O(min(N, M)).
Brute Force Approach
For each element in arr1, search and remove from arr2. Time O(N*M).
Verified Code Solutions
function solution(arr1, arr2) {
const map1 = {};
const map2 = {};
const result = [];
for (let num of arr1) {
if (map1[num]) {
map1[num]++;
} else {
map1[num] = 1;
}
}
for (let num of arr2) {
if (map2[num]) {
map2[num]++;
} else {
map2[num] = 1;
}
}
for (let num in map1) {
if (map2[num]) {
const minCount = Math.min(map1[num], map2[num]);
for (let i = 0; i < minCount; i++) {
result.push(parseInt(num));
}
}
}
return result;
}class Solution {
public:
vector<int> solution(vector<int>& arr1, vector<int>& arr2) {
unordered_map<int, int> map1;
unordered_map<int, int> map2;
vector<int> result;
for (int num : arr1) {
map1[num]++;
}
for (int num : arr2) {
map2[num]++;
}
for (auto& pair : map1) {
if (map2.find(pair.first) != map2.end()) {
int minCount = min(pair.second, map2[pair.first]);
for (int i = 0; i < minCount; i++) {
result.push_back(pair.first);
}
}
}
return result;
}
}import java.util.*;
class Solution {
public int[] solution(int[] arr1, int[] arr2) {
Map<Integer, Integer> map1 = new HashMap<>();
Map<Integer, Integer> map2 = new HashMap<>();
List<Integer> result = new ArrayList<>();
for (int num : arr1) {
map1.put(num, map1.getOrDefault(num, 0) + 1);
}
for (int num : arr2) {
map2.put(num, map2.getOrDefault(num, 0) + 1);
}
for (int num : map1.keySet()) {
if (map2.containsKey(num)) {
int minCount = Math.min(map1.get(num), map2.get(num));
for (int i = 0; i < minCount; i++) {
result.add(num);
}
}
}
int[] res = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
res[i] = result.get(i);
}
return res;
}
}def solution(arr1, arr2):
map1 = {}
map2 = {}
result = []
for num in arr1:
if num in map1:
map1[num] += 1
else:
map1[num] = 1
for num in arr2:
if num in map2:
map2[num] += 1
else:
map2[num] = 1
for num in map1:
if num in map2:
min_count = min(map1[num], map2[num])
result.extend([int(num)] * min_count)
return resultfunction solution(arr1, arr2) {
const map1 = {};
const map2 = {};
const result = [];
for (let num of arr1) {
if (map1[num]) {
map1[num]++;
} else {
map1[num] = 1;
}
}
for (let num of arr2) {
if (map2[num]) {
map2[num]++;
} else {
map2[num] = 1;
}
}
for (let num in map1) {
if (map2[num]) {
const minCount = Math.min(map1[num], map2[num]);
for (let i = 0; i < minCount; i++) {
result.push(parseInt(num));
}
}
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.