Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Each input string pairs a visit count with a domain, such as "9001 discuss.leetcode.com". A visit to that domain also counts as a visit to every parent domain: leetcode.com and com in this example. The task is to total the visits for every full domain and parent subdomain that appears implicitly or explicitly in the input. The output order does not matter.

The central detail is that counts from different records overlap. If one record contributes visits to google.mail.com and another contributes visits to intel.mail.com, both contribute to mail.com and com. A hash table is therefore a natural accumulator: each subdomain is a key, and its value is the running total.

Deriving the optimal approach

Consider one count-paired domain at a time. First split at the space to separate the integer count from the full domain. The full domain is always one required key. Every dot then marks the start of one more parent subdomain: the characters after the first dot form the next parent, the characters after the second dot form the next one, and so on.

For discuss.leetcode.com, scanning from left to right yields exactly these suffixes:

  1. discuss.leetcode.com
  2. leetcode.com
  3. com

Add the record’s count to each suffix in the hash table. Repeating this process for every record automatically combines all overlaps. There is no need to compare domains with one another because equal strings land in the same hash-table entry.

If the input contains a total of $C$ characters and produces $S$ characters across all generated suffixes, the running time is $O(C + S)$. Under the problem’s limit of at most three labels per domain, this simplifies to $O(C)$. If there are $U$ distinct subdomains, the counting table and returned answer use $O(U)$ entries, excluding the strings that must appear in the output.

Python solution

from collections import defaultdict
from typing import DefaultDict, Iterator, List, Tuple


class Solution:
    def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
        """Return the total visit count for every represented subdomain."""
        visits_by_domain: DefaultDict[str, int] = defaultdict(int)

        for count_paired_domain in cpdomains:
            visit_count, full_domain = self._parse_count_paired_domain(
                count_paired_domain
            )

            # The full domain and every suffix after a dot are precisely the
            # domains that receive this record's visits.
            for subdomain in self._iter_subdomains(full_domain):
                visits_by_domain[subdomain] += visit_count

        # LeetCode accepts the result in any order, so no sorting is needed.
        return [
            f"{visit_count} {domain}"
            for domain, visit_count in visits_by_domain.items()
        ]

    @staticmethod
    def _parse_count_paired_domain(record: str) -> Tuple[int, str]:
        """Split a record such as '9001 discuss.leetcode.com'."""
        visit_count_text, domain = record.split(maxsplit=1)
        return int(visit_count_text), domain

    @staticmethod
    def _iter_subdomains(full_domain: str) -> Iterator[str]:
        """Yield a domain followed by each of its parent subdomains."""
        yield full_domain

        for character_index, character in enumerate(full_domain):
            if character == ".":
                yield full_domain[character_index + 1 :]

Interview follow-ups

How would the solution change if the output had to be deterministic?

The counting logic would stay the same. After aggregation, sort the hash-table entries by the requested key, such as the domain name alphabetically or the visit count in descending order with the domain as a tie-breaker. Sorting makes repeated runs produce the same order, but it raises the final-stage cost from $O(U)$ to $O(U \log U)$ for $U$ distinct subdomains. If only presentation order changes, keeping sorting out of the counting loop preserves the simpler linear aggregation.

What if domains could have any number of labels?

The implementation already handles arbitrary depth because it yields one suffix after every dot. This works because each parent of a domain is uniquely identified by removing one or more leading labels. With deeper domains, however, suffix creation can no longer be treated as constant work per record: the accurate bound is the total length of all suffix strings produced. That cost is necessary if every distinct suffix must be stored and returned, although a trie can share label storage when memory pressure makes repeated suffix text expensive.

How would this work for a stream too large for one machine’s memory?

Each record can be expanded independently into (subdomain, count) contributions, which makes the problem a good fit for partitioned aggregation. Workers generate contributions and route equal subdomains to the same partition; each partition then sums its local counts. This is correct because integer addition is associative and commutative, so partial sums can be combined in any order. The computation remains linear in the emitted contributions, while network traffic and partition skew become the main tradeoffs. A very common top-level domain such as com may need local pre-aggregation before shuffling to avoid a hot partition.

How would you support live additions, removals, and count queries?

Maintain the same hash table as persistent state. An added record increments every suffix, a removed record decrements the same suffixes, and a query reads one key directly. The invariant remains that each stored value equals the sum of all active records contributing to that subdomain. An update costs $O(d)$ hash-table operations for a domain with $d$ labels, and a query is expected $O(1)$. Production code should reject removals that exceed the recorded contribution and delete entries whose counts reach zero; tracking accepted records may require additional memory if removals must be validated exactly.

How would you return only the $k$ most visited subdomains?

First compute the exact totals, then scan the $U$ aggregated entries with a min-heap of size $k$. The heap retains the best $k$ candidates seen so far, giving $O(U \log k)$ selection time and $O(k)$ extra space, compared with $O(U \log U)$ time to sort every entry. The hash table is still required for exact totals unless the input is already aggregated or an approximate streaming answer is acceptable. A deterministic tie rule, such as alphabetical domain order, should be included in the heap key.