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

Question

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
      });
  }

Answer 1

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;
}

Answer 2

Naming

a, b, what are not meaningful, descriptive and searchable names. arr1, arr2 and needle are descriptive names.

Code Duplication

There are two for loops in countInArray and both are same. A function can be created which will take array and needle as arguments and return the count.

Implicit globals

In below code, x is global. Since, var is not used to declare the variable, it is added to global scope. To make it local to function use var, let or const. See Why are global variables considered bad practice?

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

Missing Semi-Colons

Although a minor thing, but this could lead to unexpected results in some cases. I recommend to add semi-colons explicitly and not rely on automatic semicolon insertion. See What are the rules for JavaScript's automatic semicolon insertion (ASI)?

Taking advantage of ES2015

include is used in code which means that your environment supports ES2015. However, you're not taking advantage of ES2015 features.

---

With the last point above, I'll suggest you to use below equivalent code

function customMergeArrays(arr1, arr2) {
    'use strict';

    let elementCount = (haystack, needle) => haystack.filter(el => el === needle).length;
    let uniqueElements = [...new Set(arr1.concat(arr2))];

    let result = [];
    uniqueElements.forEach(function(el) {
        let aIncludes = arr1.includes(el);
        let bIncludes = arr2.includes(el);

        if ((aIncludes && bIncludes === false) || (aIncludes === false && bIncludes)) {
            result.push(el);
        } else if (aIncludes && bIncludes && elementCount(arr1, el) === elementCount(arr2, el)) {
            result.push(el);
        }
    });
    return result.sort((a, b) => a - b);
}

let firstArr = [1, 3, 40, 40, 50, 60, 60, 60];
let secondArr = [2, 40, 40, 50, 50, 65];
let mergedArray = customMergeArrays(firstArr, secondArr);
console.log(mergedArray);

Explanation:

Strict mode

elementCount is the function that uses new Arrow function and returns the count of the element occurred in the array. This method accepts array and element to search.

[...new Set(arr1.concat(arr2))] first concats two arrays and pass it to Set and using spread syntax array of unique elements is created from set.

Then, iterating over this array of unique elements and push them into results array by checking the conditions.

To compare the performance, I've created JSPerf test.