CODEWITHSUNDEEP
javascriptalgorithmecmascript-6hashanagram
Ollie Cee
Ollie Cee

Reputation: 704

Time, space complexity for my JS anagram map solution

The current setup, A and B could be larger anagrams but I chose a simple example here.

The goal is to find an index mapping P, from A to B. A mapping P[i] = j means the [n]th element in A appears in B at index j.

const A = [12, 28, 46, 32, 50]
const B = [50, 12, 32, 46, 28]

const hash = B.reduce((acc,cur,idx) => ({ ...acc, [cur]: idx }), {});

const result = A.reduce((acc,cur) => [...acc, hash[cur]], []);

return result

The result should be

[1, 4, 3, 2, 0]

What I think the time/space complexity for my solution is:
hash: time = O(a), space = O(c)
result: time = O(b), space = O(d)
Final answer is time = O(a + b), space = O(c + d)
Final final answer for time and space is O(n)?

Even though the result is being generated using time O(1) because of the hash, overall I think the time is O(n) cause n is the numbers. Am I correct in thinking this?

What is everyone thought on this? (If I'm right or wrong, not sure).

I figured some of you would ask why not use indexOf(), from my research, it looks like under the hood its a loop so I would be running O(2n). So medium to large size anagrams would be fatal.

Upvotes: 0

Views: 245

Answers (1)

Klaycon
Klaycon

Reputation: 11080

The spread operator (...acc) is an O(n) operation over the object being spread. This hits your time complexity quite a bit.

Also, since A and B are anagrams you can use the same symbol n for both as they will have the same length.

I'm not sure about space complexity but I think the time complexity will be:

hash: time = O(n^2)

result: time = O(n^2)

Final answer is time = O(2n^2) which is ~O(n^2).

Suggested improvements:

  • Don't use spread operator, it's unnecessary and slow.
  • Array.map instead of Array.reduce for the result is much cleaner
  • hash isn't hashing anything so the name is unclear, it's more of a mapping of numbers to indices - map is more clear

const A = [12, 28, 46, 32, 50]
const B = [50, 12, 32, 46, 28]

const map = B.reduce((acc,cur,idx) => { acc[cur] = idx; return acc; }, {});
const result = A.map(cur => map[cur]);

console.log(result);

This version is a pretty straightforward O(2n) -> ~O(n).

Upvotes: 2

Related Questions