Subdomain Visit Count
MedPrompt
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 thatdiscuss.leetcode.comwas visited9001times.
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.repiis an integer in the range[1, 104].d1i,d2i, andd3iconsist of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach first processes each input string to generate all possible subdomains along with their visit counts. These (count, subdomain) pairs are stored in an intermediate list. After generating all pairs from all input strings, we iterate through this list to aggregate the counts for each unique subdomain. This aggregation involves another nested loop, making it less efficient.
Algorithm
- Create a helper class or structure to hold
(count, domain)pairs. - Initialize an empty list,
allPairs, to store these pairs. - Iterate through each
cpdomainstring in the input array:- Parse the string to get the initial
countand thefullDomain. - Use a loop and string manipulation functions like
indexOf('.')andsubstring()to find all subdomains (e.g.,discuss.leetcode.com,leetcode.com,com). - For each generated subdomain, create a pair with the original count and add it to the
allPairslist.
- Parse the string to get the initial
- Initialize an empty list for the final results,
resultList, and aSetto track processed domains,processedDomains. - Iterate through the
allPairslist (outer loop).- For each pair, get its
domain. - If the
domainis inprocessedDomains, skip it. - If not, initialize
totalCount = 0. - Start an inner loop, iterating through
allPairsagain. - If a pair in the inner loop has the same domain, add its count to
totalCount. - After the inner loop finishes, add the formatted string
totalCount + " " + domaintoresultList. - Add the
domaintoprocessedDomainsto avoid recounting.
- For each pair, get its
- Return
resultList.
Walkthrough
This method breaks the problem into two main phases: generation and aggregation. First, it generates a comprehensive list of every single subdomain visit. For example, "900 google.mail.com" would generate three entries in a list: (900, "google.mail.com"), (900, "mail.com"), and (900, "com"). After this list is populated with data from all input strings, a second phase begins. This phase calculates the total count for each unique domain by iterating through the generated list. For each domain, it performs another full scan of the list to sum up the counts, which is computationally expensive.
import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public List<String> subdomainVisits(String[] cpdomains) { // A simple class to hold the pair class Pair { int count; String domain; Pair(int count, String domain) { this.count = count; this.domain = domain; } } List<Pair> allPairs = new ArrayList<>(); for (String cpdomain : cpdomains) { String[] parts = cpdomain.split(" "); int count = Integer.parseInt(parts[0]); String domain = parts[1]; while (true) { allPairs.add(new Pair(count, domain)); int dotIndex = domain.indexOf('.'); if (dotIndex == -1) { break; } domain = domain.substring(dotIndex + 1); } } List<String> result = new ArrayList<>(); Set<String> processedDomains = new HashSet<>(); for (Pair p1 : allPairs) { if (processedDomains.contains(p1.domain)) { continue; } int totalCount = 0; for (Pair p2 : allPairs) { if (p1.domain.equals(p2.domain)) { totalCount += p2.count; } } result.add(totalCount + " " + p1.domain); processedDomains.add(p1.domain); } return result; }}Complexity
Time
O(S + N^2 * L), where N is the number of `cpdomains`, L is the maximum length of a domain, and S is the total number of characters in the input. Generating all pairs takes O(S). The aggregation step involves nested loops over a list of size O(N), with string comparisons of length O(L), resulting in O(N^2 * L) complexity. For the given constraints, this is dominated by the O(N^2 * L) term.
Space
O(S), where S is the total number of characters in the input array. This space is used to store the intermediate list of all subdomain pairs (`allPairs`) and the set of processed domains (`processedDomains`).
Trade-offs
Pros
Conceptually simple, breaking the problem into two distinct phases: generation and aggregation.
Does not require knowledge of more complex data structures like hash maps.
Cons
Highly inefficient due to the nested loop for aggregation, leading to a quadratic time complexity relative to the number of input domains.
Uses significant intermediate storage for the list of all pairs before aggregation.
This is the optimal approach. It uses a hash map to store the visit counts for each subdomain. We iterate through the input array once. For each count-paired domain, we parse it, generate all its subdomains, and update their counts directly in the hash map. This avoids any repeated computations or nested loops for aggregation. Finally, we convert the map entries into the required output format.
Algorithm
- Initialize a
HashMap<String, Integer>calledcountsto store the visit count for each subdomain. - Iterate through each string
cpdomainin the input arraycpdomains. - For each
cpdomain:- Parse the string to get the
countand the fulldomain. - Use a
whileloop that continues as long as thedomainstring is valid. - In the loop, add the
countto the currentdomain's entry in thecountsmap. Usemap.getOrDefault(key, 0)to handle domains seen for the first time. - Find the index of the first dot (
.) in the currentdomain. - If a dot is found, update
domainto be the substring after the dot (e.g.,discuss.leetcode.combecomesleetcode.com). - If no dot is found, break the loop.
- Parse the string to get the
- After processing all
cpdomains, initialize an emptyArrayList<String>for the results. - Iterate through the key-value pairs in the
countsmap. - For each pair
(domain, count), create the formatted stringcount + " " + domainand add it to the result list. - Return the result list.
Walkthrough
The core idea of this efficient approach is to use a hash map for on-the-fly aggregation. As we process each line from the input, we immediately update the counts for all associated subdomains. This eliminates the need for an intermediate list and a separate, costly aggregation step. The hash map provides (on average) constant-time access for retrieving and updating counts, making the entire process very fast.
For example, when processing "900 google.mail.com", we update the counts for "google.mail.com", "mail.com", and "com" right away. When we later process "1 intel.mail.com", we simply add 1 to the existing counts for "mail.com" and "com".
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class Solution { public 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; }}Complexity
Time
O(S), where S is the total number of characters in the `cpdomains` array. For each `cpdomain`, we iterate through it to parse and generate subdomains. Let N be the number of `cpdomains` and L be the average length of a domain. The complexity is O(N * L), which is equivalent to O(S).
Space
O(S), where S is the total number of characters in the `cpdomains` array. In the worst case, every generated subdomain is unique, and we would need to store all of them in the hash map. The total length of all subdomains is proportional to S.
Trade-offs
Pros
Highly efficient with a linear time complexity relative to the total number of characters in the input.
Processes and aggregates counts in a single pass, avoiding redundant work.
The use of a hash map provides average O(1) time complexity for lookups and insertions (amortized, though string operations dominate), making the aggregation step very fast.
Cons
Requires extra space for the hash map, which can be proportional to the total size of the input if all subdomains are unique.
Solutions
Solution
class Solution { public List < String > subdomainVisits ( String [] cpdomains ) { Map < String , Integer > cnt = new HashMap <>(); for ( String s : cpdomains ) { int i = s . indexOf ( " " ); int v = Integer . parseInt ( s . substring ( 0 , i )); for (; i < s . length (); ++ i ) { if ( s . charAt ( i ) == ' ' || s . charAt ( i ) == '.' ) { String t = s . substring ( i + 1 ); cnt . put ( t , cnt . getOrDefault ( t , 0 ) + v ); } } } List < String > ans = new ArrayList <>(); for ( var e : cnt . entrySet ()) { ans . add ( e . getValue () + " " + e . getKey ()); } return ans ; } }class Solution {public: vector<string> subdomainVisits(vector<string> &cpdomains) { unordered_map<string, int> cnt; for (auto &s : cpdomains) { int i = s.find(' '); int v = stoi(s.substr(0, i)); for (; i < s.size(); ++i) { if (s[i] == ' ' || s[i] == '.') { cnt[s.substr(i + 1)] += v; } } } vector<string> ans; for (auto &[s, v] : cnt) { ans.push_back(to_string(v) + " " + s); } return ans; }};from collections import Counter class Solution : def subdomainVisits ( self , cpdomains : List [ str ]) -> List [ str ]: cnt = Counter () for s in cpdomains : v = int ( s [: s . index ( ' ' )]) for i , c in enumerate ( s ): if c in ' .' : # space ' ' is for the full domain, and '.' for subdomain cnt [ s [ i + 1 :]] += v return [ f ' { v } { s } ' for s , v in cnt . items ()] ############ class Solution ( object ): def subdomainVisits ( self , cpdomains ): """ :type cpdomains: List[str] :rtype: List[str] """ domain_counts = collections . defaultdict ( int ) for cpdomain in cpdomains : times , domains = cpdomain . split () times = int ( times ) domain_counts [ domains ] += times while '.' in domains : domains = domains [ domains . index ( '.' ) + 1 :] domain_counts [ domains ] += times return [ str ( v ) + ' ' + d for d , v in domain_counts . items ()]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.