0

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.

Ollie Cee
  • 704
  • 1
  • 6
  • 14
  • 1
    The careless use of the spread operator probably destroys your time and space complexities. Also, it's not a "hash", it's maybe a hashmap, or just a map (also see the built in `Map`). I don't fully understand, what the task for the code is, but what if some numbers occur more than once? What, if it is not an anagram, and there is no `hash[cur]`? What, if they are not even the same length? – ASDFGerte Dec 23 '19 at 21:22
  • What are `a`, `b`, `c` and `d` supposed to represent? – Bergi Dec 23 '19 at 22:00
  • @ASDFGerte its a find anagram mapping of their indices. Non anagrams aren't given or considered and only anagrams will be given. – Ollie Cee Dec 24 '19 at 00:19

1 Answers1

2

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

Klaycon
  • 10,599
  • 18
  • 35