Imagine you’re reading through a long list of visitors and want to know whether a name has shown up before. You could look back through every earlier name each time. However, as the list grows, you’d end up rereading the same names over and over. A set lets you keep the names you’ve already seen and check membership as you go.
Sometimes remembering a name is only part of the job. If you also need its count or position, you can keep that information in a Python dictionary. Here’s how the stored counts change as each color in a short list arrives:
After reading "blue", "gold", "blue", your dictionary holds two occurrences of blue and one of gold. Before you read the next item, those counts describe everything you’ve processed so far. That’s the fact you keep true each time you update the dictionary.
Pick what to store based on the question you’re answering. A set can tell you whether a color appeared. To tell two blue items apart from one, you’ll need counts. Python’s Counter gives you a convenient way to collect them, and its official documentation lists extras like .most_common().
Dictionary and set lookups take O(1) time on average. A bounded number of lookups for each of n items therefore takes O(n) time on average. Keep in mind that the stored entries use space too, so include them in your explanation. As you work through the next exercises, watch for an earlier scan that you can replace with information you’ve already saved.
