Our first optimization
lets take a look at update
Map And Set Are Not Always The Right Answer
This may sound a bit counter intuitive, but Set/Map may not always be the best option...
"And, yes, my recomendation is to use std::vector by default. More generally, use a contiguous representation unless there is a good reason not to." - Bjarne Stroustrup, Creator of C++
Plug
If you don't know the difference between an Array and a Set check out
FRONTEND MASTERS FREE FOREVER COURSE, The Last Algorithm's Course You
Need
Lets try to prove this
Then we can talk about the why behind sets