Skip to content

Instantly share code, notes, and snippets.

@imaginate
Last active August 29, 2015 14:19
Show Gist options
  • Save imaginate/98c4be83c007734e85fb to your computer and use it in GitHub Desktop.
Save imaginate/98c4be83c007734e85fb to your computer and use it in GitHub Desktop.
An efficient way to find duplicates in JavaScript - specifically the duplicate objects of two arrays. Time: O(m) | Space: O(n)
/**
* -----------------------------------------------
* Function (findDuplicates)
* -----------------------------------------------
* @desc Find the duplicate objects in two arrays. With m representing
* the length of the longest array and n the length of both arrays
* combined, this function operates in - Time: O(m) | Space: O(n).
* @param {Array<Object>} arr1 - The first array.
* @param {Array<Object>} arr2 - The second array.
* @return {Array<Object>} The duplicates.
*/
function findDuplicates(arr1, arr2) {
/** @type {Array<Object>} */
var maxArr;
/** @type {Array<Object>} */
var minArr;
/** @type {number} */
var maxLen;
/** @type {number} */
var minLen;
/** @type {Object<string, number>} */
var hashMap;
/** @type {Array<Object>} */
var duplicates;
/** @type {number} */
var i;
/** @type {string} */
var propString;
maxArr = (arr1.length > arr2.length) ? arr1 : arr2;
minArr = (arr1.length < arr2.length) ? arr1 : arr2;
maxLen = maxArr.length;
minLen = minArr.length;
hashMap = {};
duplicates = [];
i = maxLen;
while (i--) {
// Add maxArr item to hash map or duplicates
propString = makePropString( maxArr[i] );
if ( hashMap.hasOwnProperty(propString) ) {
duplicates.push( maxArr[i] );
++hashMap[ propString ];
}
else {
hashMap[ propString ] = 1;
}
// Add minArr item to hash map or duplicates
if (i < minLen) {
propString = makePropString( minArr[i] );
if ( hashMap.hasOwnProperty(propString) ) {
duplicates.push( minArr[i] );
++hashMap[ propString ];
}
else {
hashMap[ propString ] = 1;
}
}
}
return duplicates;
}
/**
* -----------------------------------------------
* Function (makePropString)
* -----------------------------------------------
* @desc Make a string of the object's unique properties.
* @param {Object<string, *>} obj - The object.
* @return {string} The property string.
*/
function makePropString(obj) {
/** @type {string} */
var prop;
/** @type {string} */
var propString;
propString = '';
for (prop in obj) {
if ( obj.hasOwnProperty(prop) ) {
propString += prop + String( obj[ prop ] );
}
}
return propString;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment