How do you solve Subdomain Visit Count?

Iterate over each count-paired domain, split it into count and domain, then split the domain by dots. For each suffix subdomain, update its count in a hash map. Finally, construct the result list by concatenating counts and subdomains from the hash map. This approach guarantees a single pass over the input and efficient aggregation.

Subdomain Visit Count

Q: What is the time complexity of Subdomain Visit Count?

O(N * M). Each of the N count-paired domains is processed once. Splitting each domain into M parts and iterating over all suffixes results in O(M) operations per domain, leading to O(N * M) total time.

Q: What pattern does Subdomain Visit Count use?

The Pattern: Hash Maps (Frequency Counting with String Manipulation) The Heuristic: When counting occurrences of hierarchical or nested keys (like subdomains), break the keys into components and aggregate counts for all suffixes or prefixes using a hash map to achieve efficient frequency accumulation.

Medium Hash Maps

Problem

Given a list of count-paired domains, return the count of visits to each subdomain.

1 ≤ cpdomains.length ≤ 100
Each cpdomain follows the format "count domain"
The count is a positive integer not exceeding 10⁴
The domain consists of lowercase English letters, digits, and dots

Example

Input: cpdomains = ["9001 discuss.leetcode.com"]

Output: ["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]

The input means there were 9001 visits to 'discuss.leetcode.com'. A visit to this domain also counts as a visit to each parent domain: 'discuss.leetcode.com', 'leetcode.com', and 'com'. The algorithm splits the domain into parts and builds every suffix subdomain, adding 9001 visits to each one.

Approach

Straightforward Solution

A naive approach might attempt to parse each domain and count visits for each possible subdomain separately without aggregation, leading to redundant computations and inefficient lookups.

Core Observation

Each visit count applies not only to the full domain but also to all its parent subdomains. This means the problem reduces to aggregating counts for all suffixes of the domain split by dots.

Path to Optimal

Preview

The key insight is to use a hash map to accumulate counts for each subdomain. By splitting each domain into parts and iterating over all suffixes, the algorithm aggregates counts in a single pass…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate over each count-paired domain, split it into count and domain, then split the domain by dots. For each suffix subdomain, update its count in a hash map…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(N * M)

Each of the N count-paired domains is processed once. Splitting each domain into M parts and iterating over all suffixes results in O(M) operations per domain, leading to O(N * M) total time.

Space

O(N * M)

In the worst case, each domain has M subdomains, and all are unique, requiring O(N * M) space in the hash map to store counts.

Pattern Spotlight

Hash Maps (Frequency Counting with String Manipulation)

When counting occurrences of hierarchical or nested keys (like subdomains), break the keys into components and aggregate counts for all suffixes or prefixes using a hash map to achieve efficient frequency accumulation.

Solution

Python

1class Solution:
2    def subdomainVisits(self, cpdomains: list[str]) -> list[str]:
3        visit_counts = {}
4
5        for entry in cpdomains:
6            count_string, domain = entry.split()
7            visit_count = int(count_string)
8
9            parts = domain.split(".")
10
11            for index in range(len(parts)):
12                subdomain = ".".join(parts[index:])
13                visit_counts[subdomain] = visit_counts.get(subdomain, 0) + visit_count
14
15        result = []
16
17        for domain, count in visit_counts.items():
18            result.append(str(count) + " " + domain)
19
20        return result

Step-by-Step Solution

Aggregate Visit Counts for Each Subdomain

3visit_counts = {}
5for entry in cpdomains:
  count_string, domain = entry.split()
  visit_count = int(count_string)
  parts = domain.split(".")
  for index in range(len(parts)):
      subdomain = ".".join(parts[index:])
      visit_counts[subdomain] = visit_counts.get(subdomain, 0) + visit_count

Objective

To parse each count-paired domain and accumulate visit counts for all subdomains in a hash map.

Key Insight

Splitting the domain by dots produces all subdomain components. Iterating over these components from left to right and joining suffixes allows the algorithm to capture every subdomain from the most specific to the top-level domain. Using a hash map to accumulate counts ensures efficient aggregation without redundant computations.

Interview Quick-Check

Core Logic

Split each domain into parts and iterate over all suffixes to accumulate counts in a hash map, capturing visits to all subdomains.

State & Boundaries

Ensure the count is converted to an integer and added to existing counts or initialized if the subdomain is new.

Common Pitfalls & Bugs

Forgetting to convert the count string to an integer or incorrectly joining subdomain parts can lead to wrong counts or malformed keys.

Construct the Result List from Aggregated Counts

To transform the aggregated counts in the hash map into the required output format.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 13 Critical

visit_counts[subdomain] = visit_counts.get(subdomain, 0) + visit_count

Update the visit count for the current subdomain in the hash map.

Incrementing the count in the hash map accumulates visits from all relevant domains, ensuring accurate total counts.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why is it necessary to aggregate counts for all suffix subdomains rather than just the full domain?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Subdomain Visit Count from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Subdomain Visit Count drill

or drill a free problem

1	`class Solution:`
2	`def subdomainVisits(self, cpdomains: list[str]) -> list[str]:`
3	`visit_counts = {}`
4
5	`for entry in cpdomains:`
6	`count_string, domain = entry.split()`
7	`visit_count = int(count_string)`
8
9	`parts = domain.split(".")`
10
11	`for index in range(len(parts)):`
12	`subdomain = ".".join(parts[index:])`
13	`visit_counts[subdomain] = visit_counts.get(subdomain, 0) + visit_count`
14
15	`result = []`
16
17	`for domain, count in visit_counts.items():`
18	`result.append(str(count) + " " + domain)`
19
20	`return result`

3	`visit_counts = {}`
5	`for entry in cpdomains:`
6	`count_string, domain = entry.split()`
7	`visit_count = int(count_string)`
9	`parts = domain.split(".")`
11	`for index in range(len(parts)):`
12	`subdomain = ".".join(parts[index:])`
13	`visit_counts[subdomain] = visit_counts.get(subdomain, 0) + visit_count`