Skip to content
Advertisement

Return sequence with elements from array A except those that are present in B p times

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)?

Advertisement

Answer

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.

User contributions licensed under: CC BY-SA
2 People found this is helpful
Advertisement