Subdomain Visit Count - Practice Coding Problems

Subdomain Visit Count - Problem

A website domain like "discuss.leetcode.com" consists of various subdomains. At the top level, we have "com", at the next level, we have "leetcode.com" and at the lowest level, "discuss.leetcode.com". When we visit a domain like "discuss.leetcode.com", we will also visit the parent domains "leetcode.com" and "com" implicitly.

A count-paired domain is a domain that has one of the two formats "rep d1.d2.d3" or "rep d1.d2" where rep is the number of visits to the domain and d1.d2.d3 is the domain itself.

For example, "9001 discuss.leetcode.com" is a count-paired domain that indicates that discuss.leetcode.com was visited 9001 times.

Given an array of count-paired domains cpdomains, return an array of the count-paired domains of each subdomain in the input. You may return the answer in any order.

Input & Output

Example 1 — Basic Three-Level Domain

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

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

💡 Note: Visiting "discuss.leetcode.com" contributes 9001 visits to itself and all parent domains: "leetcode.com" and "com"

Example 2 — Multiple Domains with Overlap

$ Input: cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]

› Output: ["901 mail.com", "50 yahoo.com", "900 google.mail.com", "5 wiki.org", "5 org", "1 intel.mail.com", "951 com"]

💡 Note: Multiple domains contribute to shared parent domains: "mail.com" gets 900+1=901 visits, "com" gets 900+50+1=951 visits

Example 3 — Two-Level Domain Only

$ Input: cpdomains = ["100 facebook.com"]

› Output: ["100 facebook.com", "100 com"]

💡 Note: Two-level domain generates only itself and top-level domain "com"

Constraints

1 ≤ cplists.length ≤ 100
1 ≤ cplists[i].length ≤ 100
cplists[i] follows either the format "rep d1.d2.d3" or "rep d1.d2"
rep is an integer in the range [1, 10⁴]
d1, d2, d3 consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Count-paired domains with visit numbers

Extract Subdomains

Each domain generates multiple subdomains

Output

Accumulated visit counts for all subdomains

Key Takeaway

🎯 Key Insight: Domain visits cascade up the hierarchy - use hash map to efficiently accumulate counts for all subdomains

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is that each domain visit contributes to all its parent domains. Use a hash map to accumulate visit counts for each subdomain. Parse each input to extract count and domain, then generate all subdomains by splitting at dots. Best approach is the optimized hash map with single-pass parsing. Time: O(n×m), Space: O(n×m) where n is number of domains and m is average subdomains per domain.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Hash Map with String Processing	O(n × m)	O(n × m)	Efficiently parse domains and use hash map for frequency counting with minimal string operations
Brute Force with Hash Map	O(n × m)	O(n × m)	Parse each domain string and extract all subdomains, using hash map to count visits

Optimized Hash Map with String Processing — Algorithm Steps

Initialize hash map for domain visit counts
For each input, parse count and domain in single pass
Generate subdomains by finding dot positions in domain string
Accumulate counts in hash map and format final output

Visualization

Tap to expand

Step-by-Step Walkthrough

Single Parse

Extract count and domain in one pass

Dot Finding

Locate dot positions without splitting

Direct Accumulation

Add counts directly to hash map

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_DOMAINS 1000
#define MAX_LEN 256

struct DomainCount {
    char domain[MAX_LEN];
    int count;
};

int findDomain(struct DomainCount* domains, int size, const char* domain) {
    for (int i = 0; i < size; i++) {
        if (strcmp(domains[i].domain, domain) == 0) {
            return i;
        }
    }
    return -1;
}

char** solution(char** cpdomains, int cpdomain_size, int* returnSize) {
    struct DomainCount domains[MAX_DOMAINS];
    int domain_count = 0;
    
    for (int i = 0; i < cpdomain_size; i++) {
        // Find space separator
        char* space = strchr(cpdomains[i], ' ');
        int count = atoi(cpdomains[i]);
        char* domain = space + 1;
        
        // Add count to full domain
        int idx = findDomain(domains, domain_count, domain);
        if (idx >= 0) {
            domains[idx].count += count;
        } else {
            strcpy(domains[domain_count].domain, domain);
            domains[domain_count].count = count;
            domain_count++;
        }
        
        // Find all dot positions and create subdomains
        char* dot = strchr(domain, '.');
        while (dot) {
            char* subdomain = dot + 1;
            idx = findDomain(domains, domain_count, subdomain);
            if (idx >= 0) {
                domains[idx].count += count;
            } else {
                strcpy(domains[domain_count].domain, subdomain);
                domains[domain_count].count = count;
                domain_count++;
            }
            dot = strchr(subdomain, '.');
        }
    }
    
    // Format result
    char** result = (char**)malloc(domain_count * sizeof(char*));
    for (int i = 0; i < domain_count; i++) {
        result[i] = (char*)malloc(MAX_LEN);
        sprintf(result[i], "%d %s", domains[i].count, domains[i].domain);
    }
    
    *returnSize = domain_count;
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON parsing for array of strings
    char* cpdomains[100];
    int count = 0;
    
    char* start = strchr(line, '"');
    while (start) {
        start++;
        char* end = strchr(start, '"');
        if (!end) break;
        
        int len = end - start;
        cpdomains[count] = (char*)malloc(len + 1);
        strncpy(cpdomains[count], start, len);
        cpdomains[count][len] = '\0';
        count++;
        
        start = strchr(end + 1, '"');
    }
    
    int returnSize;
    char** result = solution(cpdomains, count, &returnSize);
    
    // Output as JSON array
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("\"%s\"", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n input domains, each generating average m subdomains

✓ Linear Growth

Space Complexity

O(n × m)

Hash map stores all unique subdomains across all inputs

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~15 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Hash Map with String Processing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler