Editorialist: Lalit Kundu
Given N dolls of size A1, A2 … AN.
A Matryoshka doll refers to a set of wooden dolls of strictly decreasing size, placed one inside the other. Any doll can contain only one doll directly inside it.
Output “YES” if it is possible to nest them all and have one doll on the outside and “NO” otherwise.
If any two dolls have same size, we can never nest them together. Otherwise, we just sort them in decreasing order and nest them.
So, we just have to check if there are any two numbers same in a list.
We can do this in many ways:
- sort and check adjacent elements. Complexity: O(N log N)
- check for each pair of i,j if Ai == Aj. Complexity: O(N * N)
- Mark flag[Ai], for all i and check each element of flag array. Complexity: O(MAX[Ai]).
- Use set from STL in C++ and keep inserting in order. If same element find already answer is NO. Complexity: O(N log N).