811. Subdomain Visit Count - Solution

Q: Is Subdomain Visit Count easy or hard?

The problem is generally classified as Medium difficulty. The main challenge is recognizing that each domain contributes to multiple suffix subdomains and implementing the aggregation efficiently with a hash map.

Q: Subdomain Visit Count Python/Java solution

In both Python and Java, the common approach splits the input string to extract the count and domain, generates all suffix subdomains, and updates a hash map. Python typically uses a dictionary, while Java uses a HashMap for O(1) average updates.

Q: How to solve Subdomain Visit Count in O(n)?

Process each domain string once, split it into segments, and generate subdomains by iteratively removing the leftmost label. Store counts in a hash map so each update is O(1). Since each segment is processed a constant number of times, the overall complexity becomes O(n * k).

Q: What is the best approach for Subdomain Visit Count?

The hash map accumulation approach is the most practical solution. For each domain entry, split the domain into its subdomains and add the visit count to each using a hash map. This runs in O(n * k) time where n is the number of entries and k is the number of domain segments.

Q: Is Subdomain Visit Count asked at Google/Amazon/Meta?

Subdomain aggregation and log-count problems appear frequently in interviews at companies like Amazon, Google, and Meta. They test hash map usage, string parsing, and the ability to reason about hierarchical data.

Q: What data structure is used in Subdomain Visit Count?

A hash table (hash map) is the primary data structure used to accumulate counts for each subdomain. Some implementations also use a trie to represent domain hierarchy and aggregate counts along the path.

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

The optimal solution runs in O(n * k) time. Each input domain is split into k segments, and every suffix subdomain is processed once. Space complexity is O(m) to store counts for all unique subdomains.

The problem

A website domain "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.

Example 1:

Input: cpdomains = ["9001 discuss.leetcode.com"]
Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
Explanation: We only have one website domain: "discuss.leetcode.com".
As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

Example 2:

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"]
Explanation: We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times.
For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.

Constraints:

1 <= cpdomain.length <= 100
1 <= cpdomain[i].length <= 100
cpdomain[i] follows either the "rep_i d1_i.d2_i.d3_i" format or the "rep_i d1_i.d2_i" format.
rep_i is an integer in the range [1, 10⁴].
d1_i, d2_i, and d3_i consist of lowercase English letters.

Approach overview

Problem Overview: Each input string contains a visit count and a domain like "9001 discuss.leetcode.com". Every subdomain of that domain also receives the same visits. For example, discuss.leetcode.com contributes to leetcode.com and com. The task is to aggregate total visits for every possible subdomain.

Approach 1: Map-based Accumulation (O(n * k) time, O(m) space)

This approach uses a hash table to accumulate counts for each subdomain. For every input entry, split the string into the visit count and the domain. Then repeatedly strip the leftmost label of the domain to generate all subdomains. For discuss.leetcode.com, generate discuss.leetcode.com, leetcode.com, and com. Add the visit count to each key in the map. The complexity is O(n * k), where n is the number of entries and k is the number of domain segments processed per string. Space complexity is O(m) for storing distinct subdomains. This approach relies heavily on string manipulation and count aggregation, making it straightforward and efficient for interview settings.

Approach 2: Trie-based Approach (O(n * k) time, O(m) space)

A trie can represent the hierarchy of domain segments. Instead of processing domains left-to-right, reverse the domain parts and insert them into the trie from top-level domain downward. For example, split discuss.leetcode.com into ["discuss","leetcode","com"] and insert as com → leetcode → discuss. Each node stores the accumulated visit count for that partial domain. When inserting a domain, propagate the visit count through each level. Traversing the trie afterward reconstructs subdomains and their totals. Time complexity remains O(n * k) because each domain segment is processed once per entry. Space complexity is O(m), where m represents the total nodes created in the trie. This structure becomes useful when you want efficient hierarchical aggregation or repeated prefix queries.

Recommended for interviews: The map-based accumulation method is the expected solution. It demonstrates clean use of a hash map, careful string splitting, and simple iteration logic. Interviewers usually look for the insight that every domain contributes counts to all of its suffix subdomains. Implementing the trie version shows deeper understanding of hierarchical data structures, but the map approach is faster to write and easier to reason about during coding interviews.

Approach 1: Map-based Accumulation

We will use a hashmap (or dictionary) to record the visit count of each subdomain as we process each count-paired domain in the input list. By splitting each domain into its subdomains, starting from the rightmost part, we accumulate the visits to each subdomain in the map.

Python

def subdomainVisits(cpdomains):
    counts = {}
    for cpdomain in cpdomains:
        count, domain = cpdomain.split()
        count = int(count)
        fragments = domain.split('.')
        for i in range(len(fragments)):
            subdomain = '.'.join(fragments[i:])
            counts[subdomain] = counts.get(subdomain, 0) + count
    return [f"{count} {domain}" for domain, count in counts.items()]

cpdomains = ["9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
result = subdomainVisits(cpdomains)
for item in result:
    print(item)

Java

import java.util.*;

public class Solution {
    public static List<String> subdomainVisits(String[] cpdomains) {
        Map<String, Integer> counts = new HashMap<>();
        for (String cpdomain : cpdomains) {
            String[] parts = cpdomain.split(" ");
            int count = Integer.parseInt(parts[0]);
            String domain = parts[1];
            while (true) {
                counts.put(domain, counts.getOrDefault(domain, 0) + count);
                int dotIndex = domain.indexOf('.');
                if (dotIndex == -1) break;
                domain = domain.substring(dotIndex + 1);
            }
        }
        List<String> result = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            result.add(entry.getValue() + " " + entry.getKey());
        }
        return result;
    }

    public static void main(String[] args) {
        String[] cpdomains = {"9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
        List<String> result = subdomainVisits(cpdomains);
        for (String res : result) {
            System.out.println(res);
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

vector<string> subdomainVisits(vector<string>& cpdomains) {
    map<string, int> counts;
    for (const string &cpdomain : cpdomains) {
        int pos = cpdomain.find(' ');
        int count = stoi(cpdomain.substr(0, pos));
        string domain = cpdomain.substr(pos + 1);

        while (true) {
            counts[domain] += count;
            size_t next_pos = domain.find('.');
            if (next_pos == string::npos) break;
            domain = domain.substr(next_pos + 1);
        }
    }

    vector<string> result;
    for (const auto &entry : counts) {
        result.push_back(to_string(entry.second) + " " + entry.first);
    }
    return result;
}

int main() {
    vector<string> cpdomains = {"9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
    vector<string> result = subdomainVisits(cpdomains);
    for (const string &res : result) {
        cout << res << endl;
    }
    return 0;
}

JavaScript

function subdomainVisits(cpdomains) {
    let counts = {};
    cpdomains.forEach(cpdomain => {
        let [count, domain] = cpdomain.split(' ');
        count = parseInt(count);

        let fragments = domain.split('.');

        for (let i = 0; i < fragments.length; i++) {
            let subdomain = fragments.slice(i).join('.');
            counts[subdomain] = (counts[subdomain] || 0) + count;
        }
    });

    let result = [];
    for (let domain in counts) {
        result.push(`${counts[domain]} ${domain}`);
    }

    return result;
}

let cpdomains = ["9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"];
let result = subdomainVisits(cpdomains);
result.forEach(res => console.log(res));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LENGTH 100

// Define a struct for map entries
typedef struct {
    char domain[MAX_LENGTH];
    int count;
} DomainCountEntry;

// Custom hashmap-like array
typedef struct {
    DomainCountEntry *entries;
    int size;
    int capacity;
} DomainCountMap;

void initMap(DomainCountMap *map, int capacity) {
    map->entries = (DomainCountEntry *)malloc(capacity * sizeof(DomainCountEntry));
    map->size = 0;
    map->capacity = capacity;
}

void freeMap(DomainCountMap *map) {
    free(map->entries);
}

int findIndex(DomainCountMap *map, const char *domain) {
    for (int i = 0; i < map->size; i++) {
        if (strcmp(map->entries[i].domain, domain) == 0) {
            return i;
        }
    }
    return -1;
}

void insertOrUpdate(DomainCountMap *map, const char *domain, int count) {
    int index = findIndex(map, domain);
    if (index == -1) {
        // New entry
        strcpy(map->entries[map->size].domain, domain);
        map->entries[map->size].count = count;
        map->size++;
        if (map->size == map->capacity) {
            // Increase capacity
            map->capacity *= 2;
            map->entries = (DomainCountEntry *)realloc(map->entries, map->capacity * sizeof(DomainCountEntry));
        }
    } else {
        // Update existing count
        map->entries[index].count += count;
    }
}

void processDomains(const char **domains, int size, char ***result, int *resultSize) {
    DomainCountMap map;
    initMap(&map, 10);

    for (int i = 0; i < size; i++) {
        const char *cpdomain = domains[i];
        int count;
        char domain[MAX_LENGTH];
        sscanf(cpdomain, "%d %s", &count, domain);

        // Process domain
        char *token = strtok(domain, ".");
        char subdomain[MAX_LENGTH] = "";
        char buffer[MAX_LENGTH];

        while (token) {
            if (*subdomain) {
                snprintf(buffer, sizeof(buffer), "%s.%s", token, subdomain);
            } else {
                snprintf(buffer, sizeof(buffer), "%s", token);
            }
            strcpy(subdomain, buffer);
            insertOrUpdate(&map, subdomain, count);

            token = strtok(NULL, ".");
        }
    }

    // Prepare result
    *result = (char **)malloc(map.size * sizeof(char *));
    *resultSize = map.size;
    for (int i = 0; i < map.size; i++) {
        (*result)[i] = (char *)malloc(MAX_LENGTH);
        snprintf((*result)[i], MAX_LENGTH, "%d %s", map.entries[i].count, map.entries[i].domain);
    }

    freeMap(&map);
}

int main() {
    const char *cpdomains[] = {"9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
    char **result;
    int resultSize;

    processDomains(cpdomains, 5, &result, &resultSize);

    // Print results
    for (int i = 0; i < resultSize; i++) {
        printf("%s\n", result[i]);
        free(result[i]);  // Free each result
    }
    free(result);  // Free result array

    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    public static IList<string> SubdomainVisits(string[] cpdomains) {
        Dictionary<string, int> counts = new Dictionary<string, int>();
        foreach (string cpdomain in cpdomains) {
            string[] parts = cpdomain.Split(' ');
            int count = int.Parse(parts[0]);
            string domain = parts[1];

            while (true) {
                if (counts.ContainsKey(domain)) {
                    counts[domain] += count;
                } else {
                    counts[domain] = count;
                }

                int dotIndex = domain.IndexOf('.');
                if (dotIndex < 0) break;
                domain = domain.Substring(dotIndex + 1);
            }
        }

        List<string> result = new List<string>();
        foreach (KeyValuePair<string, int> entry in counts) {
            result.Add(entry.Value + " " + entry.Key);
        }
        return result;
    }

    public static void Main(string[] args) {
        string[] cpdomains = {"9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
        IList<string> result = SubdomainVisits(cpdomains);
        foreach (string res in result) {
            Console.WriteLine(res);
        }
    }
}

The Python implementation in `subdomainVisits` splits each domain into its subdomains and updates a dictionary with the counts for each subdomain. The result is constructed out of this dictionary.

Complexity

Time Complexity: O(n * m), where n represents the number of cpdomains and m is the average length of domains in components. Space Complexity: O(n * m) for dictionary storage.

Try this approach in the editor

Approach 2: Trie-based Approach

We can also implement the solution using a trie structure to track domains. Each subcomponent of a domain traverses down nodes in the trie, updating the count at each node. This approach leverages the natural hierarchy of domains efficiently through a tree structure.

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

class Solution:
    def subdomainVisits(self, cpdomains):
        root = TrieNode()

        def insert(domain, count):
            node = root
            for part in reversed(domain.split('.')):
                if part not in node.children:
                    node.children[part] = TrieNode()
                node = node.children[part]
                node.count += count

        def dfs(node, path):
            if node.count > 0:
                results.append(f"{node.count} {'.'.join(reversed(path))}")
            for part, child in node.children.items():
                dfs(child, path + [part])

        for cpdomain in cpdomains:
            count, domain = cpdomain.split()
            insert(domain, int(count))

        results = []
        dfs(root, [])
        return results

sol = Solution()
cpdomains = ["9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
result = sol.subdomainVisits(cpdomains)
for item in result:
    print(item)

Java

import java.util.*;

class Solution {
    static class TrieNode {
        Map<String, TrieNode> children = new HashMap<>();
        int count = 0;
    }

    private void insert(TrieNode root, List<String> domains, int count) {
        TrieNode node = root;
        for (int i = domains.size() - 1; i >= 0; i--) {
            if (!node.children.containsKey(domains.get(i))) {
                node.children.put(domains.get(i), new TrieNode());
            }
            node = node.children.get(domains.get(i));
            node.count += count;
        }
    }

    private void dfs(TrieNode node, String path, List<String> results) {
        if (node.count > 0) {
            results.add(node.count + " " + path);
        }
        node.children.forEach((key, child) -> {
            dfs(child, key + (path.isEmpty() ? "" : ".") + path, results);
        });
    }

    public List<String> subdomainVisits(String[] cpdomains) {
        TrieNode root = new TrieNode();
        for (String cpdomain : cpdomains) {
            String[] parts = cpdomain.split(" ");
            int count = Integer.parseInt(parts[0]);
            List<String> domainParts = Arrays.asList(parts[1].split("\\."));
            insert(root, domainParts, count);
        }

        List<String> results = new ArrayList<>();
        dfs(root, "", results);
        return results;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] cpdomains = {"9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
        List<String> result = sol.subdomainVisits(cpdomains);
        result.forEach(System.out::println);
    }
}

C++

#include <iostream>
#include <map>
#include <vector>
#include <sstream>
using namespace std;

struct TrieNode {
    map<string, TrieNode*> children;
    int count = 0;
};

void insert(TrieNode* root, vector<string>& tokens, int count) {
    TrieNode* node = root;
    for (auto it = tokens.rbegin(); it != tokens.rend(); ++it) {
        if (!node->children[*it])
            node->children[*it] = new TrieNode();
        node = node->children[*it];
        node->count += count;
    }
}

void dfs(TrieNode* node, string current, vector<string>& result) {
    if (node->count > 0) {
        result.push_back(to_string(node->count) + " " + current);
    }
    for (auto& child : node->children) {
        dfs(child.second, child.first + (current.empty() ? "" : ".") + current, result);
    }
}

vector<string> subdomainVisits(vector<string>& cpdomains) {
    TrieNode* root = new TrieNode();
    for (auto& domain : cpdomains) {
        stringstream ss(domain);
        int count;
        ss >> count;
        string dom;
        ss >> dom;
        vector<string> tokens;
        stringstream ss_tokens(dom);
        string token;
        while (getline(ss_tokens, token, '.')) {
            tokens.push_back(token);
        }
        insert(root, tokens, count);
    }
    vector<string> result;
    dfs(root, "", result);
    return result;
}

int main() {
    vector<string> cpdomains = {"9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
    vector<string> result = subdomainVisits(cpdomains);
    for (string& s : result) {
        cout << s << endl;
    }
    return 0;
}

JavaScript

function TrieNode() {
    this.children = {};
    this.count = 0;
}

function insert(root, domain, count) {
    const parts = domain.split('.');
    let node = root;
    for (let i = parts.length - 1; i >= 0; i--) {
        if (!node.children[parts[i]]) {
            node.children[parts[i]] = new TrieNode();
        }
        node = node.children[parts[i]];
        node.count += count;
    }
}

function dfs(node, path, results) {
    if (node.count > 0) {
        results.push(`${node.count} ${path.join('.')}`);
    }
    for (const part in node.children) {
        dfs(node.children[part], [part].concat(path), results);
    }
}

function subdomainVisits(cpdomains) {
    const root = new TrieNode();
    cpdomains.forEach(cpdomain => {
        const [count, domain] = cpdomain.split(' ');
        insert(root, domain, parseInt(count));
    });
    const results = [];
    dfs(root, [], results);
    return results;
}

const cpdomains = ["9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"];
const result = subdomainVisits(cpdomains);
result.forEach(res => console.log(res));

Implementing a Trie in C is non-trivial and for brevity, we will not provide a C example here. However, the concept involves creating nodes representing domain parts and traversing the trie to tally counts.

Implementing a Trie in C# efficiently would require some understanding of collections and can be similar to Java or C++ using Dictionary to represent children nodes for TrieNode class.

Similar to Java, Python's Trie insertion and depth-first search traverses and links domain parts into nodes to form valid subdomains and results after parsing input strings aptly.

Complexity

Time Complexity: Approximately O(n * m) equating to input parsing efficiency. Space Complexity: O(n * m) through intensive node and structure combination.

Try this approach in the editor

Approach 3: Default Approach

func subdomainVisits(cpdomains []string) []string {
	cnt := map[string]int{}
	for _, s := range cpdomains {
		i := strings.IndexByte(s, ' ')
		v, _ := strconv.Atoi(s[:i])
		for ; i < len(s); i++ {
			if s[i] == ' ' || s[i] == '.' {
				cnt[s[i+1:]] += v
			}
		}
	}
	ans := make([]string, 0, len(cnt))
	for s, v := range cnt {
		ans = append(ans, strconv.Itoa(v)+" "+s)
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Map-based Accumulation	Time Complexity: O(n * m), where n represents the number of cpdomains and m is the average length of domains in components. Space Complexity: O(n * m) for dictionary storage.
Trie-based Approach	Time Complexity: Approximately O(n * m) equating to input parsing efficiency. Space Complexity: O(n * m) through intensive node and structure combination.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Map-based Accumulation	O(n * k)	O(m)	Best general solution. Simple implementation using hash map and string splits.
Trie-based Approach	O(n * k)	O(m)	Useful when domain hierarchy queries or repeated prefix lookups are required.

Frequently asked questions

Is Subdomain Visit Count easy or hard?

The problem is generally classified as Medium difficulty. The main challenge is recognizing that each domain contributes to multiple suffix subdomains and implementing the aggregation efficiently with a hash map.

Subdomain Visit Count Python/Java solution

In both Python and Java, the common approach splits the input string to extract the count and domain, generates all suffix subdomains, and updates a hash map. Python typically uses a dictionary, while Java uses a HashMap for O(1) average updates.

How to solve Subdomain Visit Count in O(n)?

Process each domain string once, split it into segments, and generate subdomains by iteratively removing the leftmost label. Store counts in a hash map so each update is O(1). Since each segment is processed a constant number of times, the overall complexity becomes O(n * k).

What is the best approach for Subdomain Visit Count?

The hash map accumulation approach is the most practical solution. For each domain entry, split the domain into its subdomains and add the visit count to each using a hash map. This runs in O(n * k) time where n is the number of entries and k is the number of domain segments.

Is Subdomain Visit Count asked at Google/Amazon/Meta?

Subdomain aggregation and log-count problems appear frequently in interviews at companies like Amazon, Google, and Meta. They test hash map usage, string parsing, and the ability to reason about hierarchical data.

What data structure is used in Subdomain Visit Count?

A hash table (hash map) is the primary data structure used to accumulate counts for each subdomain. Some implementations also use a trie to represent domain hierarchy and aggregate counts along the path.

What is the time complexity of Subdomain Visit Count?

The optimal solution runs in O(n * k) time. Each input domain is split into k segments, and every suffix subdomain is processed once. Space complexity is O(m) to store counts for all unique subdomains.

Subdomain Visit Count solution and explanation

The problem

Approach overview

Approach 1: Map-based Accumulation

Approach 2: Trie-based Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Subdomain Visit Count solution and explanation

The problem

Approach overview

Approach 1: Map-based Accumulation

Approach 2: Trie-based Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems