In this question, we want to find who hasn't yet received a gift, so we can give our gift to them. In other words, we want check who sent a gift, but did not get one in return.

We should highlight that in this question:

• There is only one person who hasn't gotten a gift in return.
• We don't need to track how many times a person got a gift, only if they got a gift or not.
• A person cannot give a gift to themselves.

One way to approach this is to have two hash sets: one for storing people who sent a gift, and the other for who received a gift. For the ~n~gift exchanges, we can store the people to sent or received a gift into the respective sets. We can use hash sets since we don't care about how many times a person sent or received a gift, and we don't need to account for ordering.

Then, we can iterate over the set of sent gifts and see if the name exists in the set of received gifts. If a person who sent a gift does not exist in the set of gift recipients, then they are the person that you should give your gift to.

The time complexity of the solution is ~O(n)~. Taking in the input and then finding the person who hasn't gotten their gift are both ~O(n)~, while queries on the hash set are all ~O(1)~. It is also ~O(n)~ space complexity due to the set storing peoples names.

C++ solution: This solution leverages only a single hashmap. By storing the indegree of each person (the amount of people giving them gifts), as well as initialising unseen names to be 0 in the map (that is what the line containing just indegree[from] does), we can just loop over and find the person with indegree 0.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    unordered_map<string, int> indegree;
    int n;
    cin >> n;
    string from, to;
    while (n--) {
        cin >> from >> to;
        indegree[to]++;
        indegree[from];
    }

    for (auto [k, v] : indegree) {
        if (v == 0) cout << k << endl;
    }
}

Python solution: Set subtraction is handily defined in python, allowing us to find the person who has given a gift but not received one yet. next(iter(...)) is simply one way of grabbing the single element out of the set.

fromNames = set()
toNames = set()

n = int(input())

for _ in range(n):
    f, t = input().split()
    fromNames.add(f)
    toNames.add(t)

print(next(iter(fromNames - toNames)))