Merge two sorted arrays, make more efficent (O(a+b))

Problem :Given two sorted arrays, merge them to form a new array of unique items.


If an item is present in both arrays, it should be part of the resulting array if and only if it appears in both arrays the same number of times.


e.g.: a = [1, 3, 40, 40, 50, 60, 60, 60] and b = [2, 40, 40, 50, 50, 65],
should return [1, 2, 3, 40, 60, 65]


a = [2,2,2,2,40,40,50] and b = [40,40,60] should return [2,40,50,60]


a = [5,5] and b = [5,5,5] should return []

My problem is that my function is not efficient enough (runtime takes too long), is it possible to may it more efficient? Possibly O(a+b)

function mergeArrays(a, b) {

      function countInArray(array, array2, what) {
          var count = 0;
          var count2 = 0;

          for (var i = 0; i < array2.length; i++) {
              if (array2[i] === what) {
                  count2++;
              }
          }
          for (var i = 0; i < array.length; i++) {
              if (array[i] === what) {
                  count++;
              }
          }
          return count === count2;
      }

      var arr = []
      for (x = 0; x < b.length; x++) {
          if (!a.includes(b[x]) && !arr.includes(b[x]))
              arr.push(b[x])
      }

      for (i = 0; i < a.length; i++) {
          if (countInArray(a, b, a[i]) && !arr.includes(a[i])) {
              arr.push(a[i])
          } else {
              if (!arr.includes(a[i]) && !b.includes(a[i]))
                  arr.push(a[i])
          }
      }

      console.log(arr)
      return arr.sort(function(a, b) {
          return a - b
      });
  }

Current code

The time complexity of your current code is indeed quite high and can be made \$O(a+b)\$ as you suggest.

But first, a few remarks about the code (some of these were already covered by @Tushar while I was writing this answer):

• Nested functions: It's not very efficient to define a function inside a function. As far as I know, most JS interpreters would actually construct a new closure (simply – a new function) each time mergeArrays gets called. There's no harm in defining countInArrays next to mergeArrays, instead of inside it, and it will probably make your code faster.

-
Scope of variables:

• The for-loop variables x and i in function mergeArrays are not declared with the var or let keyword, which makes them global. That means they will exist even after your function returns. For example, you could call your function, and after it returns you could print the value of x, because it's in global scope and therefore accessible from everywhere. You probably don't want that, so it's better to use the var keyword, as you do in the countInArray function.

• However, a variable declared in a function using the var keyword has function scope. That means, if you use i in the first for and also in the second for, then the second var i = 0 is in fact a re-declaration of an already-existing variable. Fortunately ECMAScript 6 introduced the let keyword, which declares a variable within the scope of the block. That means a variable declared as for (let i = … will "cease to exist" after that for loop.

-
Ergo, if using i just within the for-loop, it's preferable to do it this way:

for (let i = 0; i < a.length; i++) …

Optimized version

@Tushar has posted a more performant version. However, if I'm not mistaken, the asymptotic time complexity of his improved version is the same as – or very similar to – the complexity of your original version.

Here is an implementation with \$O(a+b)\$ asymptotic time complexity.

A few things to note:

• there is some code duplicity and it surely could be written more nicely,

• I have not tested it very thoroughly – only on the samples you provided in your question,

• EDIT: performance benchmark.

function mergeArrays2(a, b) {

    let res = [];
    let wasInBoth;  // Indicates whether a repeating value
                    // was in both `a` and `b`.

    let i = 0;
    let j = 0;

    while (i < a.length && j < b.length) {
        const elemA = a[i];
        const elemB = b[j];

        if (elemA === elemB) {
            // Same elements – add them both if not already present.
            if (!(elemA === res[res.length - 1] && wasInBoth)) {
                res[res.length] = elemA;
                wasInBoth = true;
            }
            i++;
            j++;
            continue;
        }

        // Different elements – check if either of them is already
        // in `res` and was in both `a` and `b`. If yes, remove it
        // from `res`, because its number of occurrences in `a` and `b`
        // is not the same.
        if (wasInBoth) {
            wasInBoth = false;  // Not any more.

            if (elemA === res[res.length - 1]) {
                // `a` contains more occurrences of the element than `b`.
                // Remove the element from `res` and skip
                // all the occurrences of the element in `a`.
                res.length--;
                while (a[++i] === elemA);
                continue;
            }
            else if (elemB === res[res.length - 1]) {
                // `b` contains more occurrences of the element than `a`.
                // Remove the element from `res` and skip
                // all the occurrences of the element in `b`.
                res.length--;
                while (b[++j] === elemB);
                continue;
            }
        }

        // Different elements – select the least.
        // Add it if not already present.
        if (elemA < elemB) {
            if (elemA !== res[res.length - 1]) {
                res[res.length] = elemA;
            }
            i++;
        }
        else {
            if (elemB !== res[res.length - 1]) {
                res[res.length] = elemB;
            }
            j++;
        }
    }

    // Process the rest of `a` or `b`, whichever is not done.
    let [rest, idx]  = (i < a.length)? [a, i] : [b, j];

    while (idx < rest.length) {
        const elem = rest[idx];

        if (wasInBoth) {
            wasInBoth = false;

            if (elem === res[res.length - 1]) {
               // Same as before – remove from `res`
               // and skip all further occurrences.
                res.length--;
                while (rest[++idx] === elem);
                continue;
            }
        }

        // Same as before – add if not present.
        if (elem !== res[res.length - 1]) {
            res[res.length] = elem;
        }
        idx++;
    }

    return res;
}

StackExchange Code Review Q#160496, answer score: 5