Good evening all,
I am reaching out, as I had some questions about the editorial for ABC 277 problem C. The editorial for ABC 277 C — Ladder Takahashi states that the time complexity for the aforementioned problem is O(N * log (N)).
- Where is this logarithmic factor coming from ? Is this from the set and map data structures which take logarithmic time for insertion and search operation ?
- Would the time complexity reduce to O(N) on average if we were to use an unordered_map or unordered_set ?
YES and YES.
Personally prefer map/set over unordered_map/unordered_set in any case where logarithmic operation is not the bottleneck. Plus it's shorter to type map/set. Hash collision is another concern but it's not the issue for this problem.