### PROBLEM LINK:

**Editorialist**: Lalit Kundu

### DIFFICULTY:

CAKEWALK

### PRE-REQUISITES:

Sorting

### PROBLEM:

Given **N** dolls of size **A _{1}, A_{2} … A_{N}**.

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.

### EXPLANATION:

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**A**. Complexity:_{i}== A_{j}**O(N * N)** - Mark
**flag[A**, for all_{i}]**i**and check each element of**flag**array. Complexity:**O(MAX[A**._{i}]) - Use set from STL in C++ and keep inserting in order. If same element find already answer is NO. Complexity:
**O(N log N)**.