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.
"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 <= 1001 <= cpdomain[i].length <= 100cpdomain[i] follows either the "repi d1i.d2i.d3i" format or the "repi d1i.d2i" format.repi is an integer in the range [1, 104].d1i, d2i, and d3i consist of lowercase English letters.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.
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.
The solution initializes a map as a dynamic array implemented using a struct array. The `processDomains` function processes each count-paired domain, extracts the count, and decomposes the domain into subdomains. For each subdomain, it updates the domain visit count in the map. Finally, it prepares the result in the specified format by iterating the map entries.
Time Complexity: O(n * m) where n is the number of domains and m is the average number of subcomponents of a domain. Space Complexity: O(n * m) for storing subdomains in the map.
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.
A Trie implementation in C would involve struct definitions for nodes, containing a map to child nodes and an integer to tally counts.
Time Complexity: O(n * m), n domains and m depth. Space Complexity: Higher space use due to node allocations.
| Approach | Complexity |
|---|---|
| Map-based Accumulation | Time Complexity: O(n * m) where n is the number of domains and m is the average number of subcomponents of a domain. Space Complexity: O(n * m) for storing subdomains in the map. |
| Trie-based Approach | Time Complexity: O(n * m), n domains and m depth. Space Complexity: Higher space use due to node allocations. |
| Default Approach | — |
| 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. |
SubDomain Visit Count • Pepcoding • 2,925 views views
Watch 9 more video solutions →Practice Subdomain Visit Count with our built-in code editor and test cases.
Practice on FleetCode