Check existence of matching key,value pair I recently was in an interview where I was asked to implement a snippet that finds the matching key:value pair among two JavaScript arrays in which each member is an object:

var a = [{color:'blue'},{color:'green'}, {color:'brown'}, {color:'black'}]
var b = [{color:'white'},{color:'yellow'}, {color:'black'}, {color:'blue'}]
var expectedOutput = [{color:'blue'}, {color:'black'}]


Here's my implementation:



var a = [{color:'blue'},{color:'green'}, {color:'brown'}, {color:'black'}]
var b = [{color:'white'},{color:'yellow'}, {color:'black'}, {color:'blue'}]
var expectedOutput = [];
for(var i=0; i&lt;a.length; i++){
 if(b[i].hasOwnProperty('color') &amp;&amp; a[i].color===b[i].color){
  expectedOutput.push(a[i]);
 }
}

document.write(expectedOutput.toString());




In the interview, I communicated that using .hasOwnProperty() provides \$O(1)\$ lookup for keys (but not for values) from array b, and unfortunately, I wasn't able to fully implement this as my mind wandered across other possibilities there might be, not to mention the pressure.

I believe this still has \$O(n^2)\$ complexity as it simply checks the existence of child .color key as well as a supplementary check against values being equivalent. All in all, I suspect the interviewer was pointing me into this implementation for \$O(n)\$ complexity.

Do you think otherwise? If you do, could you kindly explain why and how? If my question is unclear, how would you solve it in \$O(n)\$ time in JavaScript?
I would say that hasOwnProperty is not necessary in this case. If you want to make it O(n) you probably have to first convert one of the arrays into a hash of colors so that you can improve lookup speed. Something like:



var a = [{color:'blue'},{color:'green'}, {color:'brown'}, {color:'black'}];
var b = [{color:'white'},{color:'yellow'}, {color:'black'}, {color:'blue'}];
var aColors = a.reduce( function(obj, hash) { obj[hash.color] = true; return obj }, {} );

var expectedOutput = [];
for(var i=0; i&lt;b.length; i++) {
 if (aColors[ b[i].color ] )
  expectedOutput.push( b[i] );
}

console.log(expectedOutput);