Prerequisites: STL’s set or map
Problem:
Luna Lovegood found a mysterious locket with the power to influence its possessor’s thoughts and actions. Harry Potter wants to ensure that no one else has been influenced by this enchanted locket before Luna. Given a list of N names of people who held the locket in sequence, determine if each person held the locket at any point before.
Solution Approach:
The core idea of the solution is to maintain a set (names) to keep track of the names of people who have previously held the locket. As we iterate through the list of names, we check whether the current name is already present in the set.
- If the name is found in the set, it means the person has held the locket before, so we print “YES”.
- If the name is not found in the set, it indicates that the person is holding the locket for the first time, so we print “NO” and then add the name to the set for future reference.
Time Complexity:
O(N) as we’re using unordered_set
Space Complexity:
O(N) as we’re storing input in set.