Determine if one array contains all elements of another array, including any duplicates

Question

I'm looking for a function that returns true if and only if a given array includes all the elements of another target array which may include two or more occurrences of the same element.

Sample data:

const target = [ 1, 3, 3 ];
const array1 = [ 1, 2, 3, 4 ]; // false
const array2 = [ 1, 3, 3, 4 ]; // true
const array3 = [ 1, 3, 4, 3 ]; // true
const array4 = [ 3, 2, 1, 3 ]; // true
const array5 = [ 1, 1, 3, 3 ]; // true

This question's answer is close but doesn't account for duplicates in target array.

This question's answer works for Ruby but I'm looking for a Javascript solution.

When not accounting for duplicates, .indexOf() and .includes() make it rather easy and there are elegant one-liner solutions. But I'm unsure how to keep track of duplicates and suspect a more iterative approach is needed.

• Barmar: Loop through the array you're testing. If the current element is in target, remove that element from target. At the end, check if target is empty.
• Barmar: If you found a solution in Ruby, how hard could it be to adapt the same algorithm to JavaScript?
• Jonas Wilms: What about [ 1, 1, 3, 3] ? True or false?
• BartmanEH: [ 1, 1, 3, 3] true
• BartmanEH: @Barmar the Ruby answer is a class I don't even know how to apply: class Array def contains_all? other other = other.dup each{|e| if i = other.index(e) then other.delete_at(i) end} other.empty? end end

Answer 1

const isMultiSubset = (target, value) => {
 const occurences = new Map;
 for(const entry of target) 
 occurences.set(entry, (occurences.get(entry) ?? 0) + 1);
 for(const entry of value)
 if (occurences.has(entry))
 occurences.set(entry, occurences.get(entry) - 1);
 return [...occurences.values()].every(count => count <= 0); 
};

By using a Map to count occurences this can be solved in O(n + m).

• BartmanEH: Thank you. I will test this out and report back.
• Hero Wanders: Great solution. A theoretical optimization would compare the resulting count against 0 in the second loop and immediately return false if decrementing would make it negative. You could also avoid checking excess elements (imagine a huge array to search in) by counting the found matches in the second loop; if they add up to target.length you could immediately return true. Practically one should measure whether the actual data is worth the additional bookkeeping and potential CPU conditional branching slowdowns.
• Hero Wanders: This is a fix for my previous comment about optimizations: when reaching 0 for an entry in the second loop, the function should NOT return immediately, that suggestion was plainly wrong. One could remove the entry from occurrences though (and the final line would then just check whether the Map is empty, meaning all desired occurrences have been matched), but it's really not obvious to me whether this would improve anything; your code is fine as is.

Answer 2

Similar to @Barmar's comment, you might also loop over the elements you want to have included and remove them from the target, if they are present and immediately return false if one of them is not present. If every desired element was found, return true.

Notice: this has time complexity O(n*m), @Jonas' solution has better time complexity.

function includesMulti(elements, inArray) {
 const unmatched = inArray.slice();
 for (const element of elements) {
 const matchIndex = unmatched.indexOf(element);
 if (matchIndex === -1) return false;
 unmatched.splice(matchIndex, 1);
 }
 return true;
}
const target = [ 1, 3, 3 ];
const array1 = [ 1, 2, 3, 4 ]; // false
const array2 = [ 1, 3, 3, 4 ]; // true
const array3 = [ 1, 3, 4, 3 ]; // true
const array4 = [ 3, 2, 1, 3 ]; // true
const array5 = [ 1, 1, 3, 3 ]; // true
const array6 = [ 1, 1, 3, 3]; // true
console.log(includesMulti(target, array1));
console.log(includesMulti(target, array2));
console.log(includesMulti(target, array3));
console.log(includesMulti(target, array4));
console.log(includesMulti(target, array5));
console.log(includesMulti(target, array6));

A refinement of this approach which avoids cloning and rescanning the array to search in could be the following: for each element to look for remember where it was found last use that as the offset for the next indexOf search.

function includesMulti(elements, inArray) {
 const lastMatches = new Map();
 for (const element of elements) {
 const previousMatchIndex = lastMatches.get(element);
 const matchIndex = inArray.indexOf(element, previousMatchIndex + 1);
 if (matchIndex === -1) return false;
 lastMatches.set(element, matchIndex);
 }
 return true;
}
const target = [ 1, 3, 3 ];
const array1 = [ 1, 2, 3, 4 ]; // false
const array2 = [ 1, 3, 3, 4 ]; // true
const array3 = [ 1, 3, 4, 3 ]; // true
const array4 = [ 3, 2, 1, 3 ]; // true
const array5 = [ 1, 1, 3, 3 ]; // true
const array6 = [ 1, 1, 3, 3]; // true
console.log(includesMulti(target, array1));
console.log(includesMulti(target, array2));
console.log(includesMulti(target, array3));
console.log(includesMulti(target, array4));
console.log(includesMulti(target, array5));
console.log(includesMulti(target, array6));

There is a little trick in here: when no previous match was found, undefined is returned from map.get and then previousMatchIndex+1 is NaN which is ignored by indexOf. To be more explicit, you might want to replace that by previousMatchIndex === undefined ? 0 : (previousMatchIndex+1).

Answer 3

Something like this maybe. It works but it is not the most performant.

const target = [1, 3, 3];
const array1 = [1, 2, 3, 4]; // false
const array2 = [1, 3, 3, 4]; // true
const array3 = [1, 3, 4, 3]; // true
const array4 = [3, 2, 1, 3]; // true
const testArray = (arr1, arr2) => {
 const countOccurrences = (arrayToCount) => {
 return arrayToCount.reduce((acc, e) => {
 acc[e] ? (acc[e] = { count: acc[e].count + 1 }) : (acc[e] = { count: 1 });
 return acc;
 }, {});
 };
 let reduced = countOccurrences(arr1);
 let reduced2 = countOccurrences(arr2);
 const result = Object.keys(reduced).reduce((acc, e) => {
 if (!acc) return false;
 if (!reduced2[e]) return false;
 if (reduced2[e].count < reduced[e].count) return false;
 return acc;
 }, true);
 return result;
};
console.log(testArray(target, array1));
console.log(testArray(target, array2));
console.log(testArray(target, array3));
console.log(testArray(target, array4));