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)
orO(n)
?
That’s the same. Constant factors are ignored in Landau notation.