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



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

StackExchange Code Review Q#162652, answer score: 2