Last active
August 29, 2015 14:19
-
-
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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* ----------------------------------------------- | |
* 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