4. Find the Group with the Most Distinct Items

Posted on One min read

1. Description

You are given a sequence of logs containing two types of operations:

  • switch group: changes the current group.
  • push item: adds an item to the current group. Adding the same item to the same group multiple times only counts once.

Return the name of the group that contains the largest number of distinct items after processing all logs.

2. Solution

n = logs.size()
Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

string solution(const vector<string>& logs) {
    unordered_map<string, unordered_set<string>> items;
    string current_group, result;

    for (const string& log : logs) {
        if (log[0] == 's') {
            current_group = log.substr(7);
        } else {
            string item = log.substr(5);
            items[current_group].insert(item);

            if (result.empty() ||
                items[current_group].size() > items[result].size()) {
                result = current_group;
            }
        }
    }

    return result;
}
comments powered by Disqus