Array Merge without Duplicates I recently saw this Javascript code on StackOverflow for merging two arrays, and removing duplicates:

Array.prototype.unique = function() {
    var a = this.concat();
    for(var i=0; i&lt;a.length; ++i) {
        for(var j=i+1; j&lt;a.length; ++j) {
            if(a[i] === a[j])
                a.splice(j--, 1);
        }
    }
    return a;
};

var array1 = ["Vijendra","Singh"];
var array2 = ["Singh", "Shakya"];
var array3 = array1.concat(array2).unique(); 


While this code works, it is horribly inefficient (O(n^2)). Your challenge is to make an algorithm with less complexity.

The winning criteria is the solution with the least complexity, but ties will be broken by shortest length in characters.

Requirements:

Package all your code together in a function that meets the following requirements for "correctness:"


Input: Two arrays
Output: One array
Merges elements of both arrays together- Any element in either input array must be in the outputted array.
The outputted array should have no duplicates.
Order doesn't matter (unlike the original)
Any language counts
Don't use the standard library's array functions for detecting uniqueness or merging sets/arrays (although other things from the standard library is okay). Let me make the distinction that array concatenation is fine, but functions that already do all of the above are not.
JavaScript O(N) 131 124 116 92 (86?)

Golfed version:

function m(i,x){h={};n=[];for(a=2;a--;i=x)i.map(function(b){h[b]=h[b]||n.push(b)});return n}


Human readable golfed version:

function m(i,x) {
   h = {}
   n = []
   for (a = 2; a--; i=x)
      i.map(function(b){
        h[b] = h[b] || n.push(b)
      })
   return n
}


I could use concat like so and do it in 86 characters:

function m(i,x){h={};n=[];i.concat(x).map(function(b){h[b]=h[b]||n.push(b)});return n}


But I am not sure if it is still O(N) based on this JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping as the concat version is marginally faster with smaller arrays but slower with larger arrays (Chrome 31 OSX).

In practice do this (golf is full of bad practices):

function merge(a1, a2) {
   var hash = {};
   var arr = [];
   for (var i = 0; i &lt; a1.length; i++) {
      if (hash[a1[i]] !== true) {
        hash[a1[i]] = true;
        arr[arr.length] = a1[i];
      }
   }
   for (var i = 0; i &lt; a2.length; i++) {
      if (hash[a2[i]] !== true) {
        hash[a2[i]] = true;
        arr[arr.length] = a2[i];
      }
   }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6]));


I'm not great at computing complexity but I believe this is O(N). Would love if someone could clarify.

Edit: Here is a version that takes any number of arrays and merges them.

function merge() {
   var args = arguments;
   var hash = {};
   var arr = [];
   for (var i = 0; i &lt; args.length; i++) {
      for (var j = 0; j &lt; args[i].length; j++) {
        if (hash[args[i][j]] !== true) {
          arr[arr.length] = args[i][j];
          hash[args[i][j]] = true;
        }
      }
    }
   return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8]));