Second Most Frequent Tag from Flattened Triples

Problem: Find the Second Most Frequent Tag from a Flattened String List You are given a string list arr whose elements repeat in the following fixed order: [id1, name1, tag1, id2, name2, tag2, ...] That is, every 3 elements form one record: id, name, tag. Count the frequency of each tag and return the second most frequent tag. Rules / Edge Cases If there is no “second most frequent” tag (e.g., all tags have the same frequency, or there is only one distinct tag), return: notag If multiple tags tie for the second highest frequency, return the one whose first occurrence in the original list is earliest. Input/Output Input: a list/array of strings arr Output: a single string: the selected tag or notag Examples Example 1: Input: [id1, n1, A, id2, n2, B, id3, n3, A, id4, n4, C, id5, n5, B, id6, n6, A] Counts: A=3, B=2, C=1 Output: B Example 2 (all equal): Input: [id1, n1, A, id2, n2, B] A=1, B=1 → no second most Output: notag Example 3 (tie for second, pick earliest first-seen): Counts: A=3, B=2, C=2 → second frequency is 2; B appears earlier than C Output: B Constraints (to confirm in interview) arr.length up to 1e5 Up to 1e5 distinct tags Target complexity: O(n) or O(n log m) Example Input id1 n1 A id2 n2 B id3 n3 A id4 n4 C id5 n5 B id6 n6 A Output B