I want to write a function that receives two sequences: A and B and returns sequence C which should contain all elements from A (in order) except those that are present in B p times.

For example sequences

A=[2,3,9,2,5,1,3,7,10]

B=[2,1,3,4,3,10,6,6,1,7,10,10,10]

Should return C=[2,9,2,5,7,10]

When p = 2

I wrote it like this:

function cSequence(a, b, p) {
  const times = {};
  b.forEach((item) => {
    if (times[item]) {
      times[item]  = 1;
    } else {
      times[item] = 1;
    }
  });
  const pTimes = b.filter((item) => (times[item] == p ? true : false));
  return a.filter((item) => !pTimes.includes(item));
}

But is there a better way to make this in terms of time complexity?

Also, should my solution be expressed as O(3n) or O(n)?

CodePudding user response：

Is there a better way to make this in terms of time complexity?

Don't use includes() inside the filter callback! That gives it a quadratic time complexity. You already have a lookup map by item, just use that directly to achieve a linear solution! Get rid of the intermediate pTimes:

function cSequence(a, b, p) {
  const times = {};
  for (const item of b) {
    if (item in times) {
      times[item]  = 1;
    } else {
      times[item] = 1;
    }
  }
  return a.filter(item => times[item] != p);
}

Should my solution be expressed as O(3n) or O(n)?

That's the same. Constant factors are ignored in Landau notation.

CodePudding user response：

You can use Array.prototype.reduce() to create bHash object that contains all the total number occurrences

And then, Array.prototype.filter() array A excluding those elements that are repeated in array B p times

Code:

const A = [2,3,9,2,5,1,3,7,10]
const B = [2,1,3,4,3,10,6,6,1,7,10,10,10]
const p = 2

const cSequence = (arrA, arrB, p) => {
  const bHash = arrB.reduce((a, c) => (a[c] ??= 0, a[c]  , a), {})
  return arrA.filter(n => bHash[n] !== p)
}

console.log(cSequence(A, B, p))