algoadvance

Leetcode 811. Subdomain Visit Count

Problem Statement

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, we also visit the parent domains automatically.

For example, if we visit “discuss.leetcode.com”, we will also visit “leetcode.com” and “com”.

Now, you are given a list cpdomains of count-paired domains. Each element in cpdomains is a string that consists of a count and a domain. The task is to calculate the number of visits to each subdomain.

Example:

Input:

["9001 discuss.leetcode.com"]

Output:

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

Clarifying Questions

1. What are the constraints on the input size?
   • The length of cpdomains will not exceed 100.
   • The length of each domain in cpdomains will not exceed 100.
   • The count in each domain entry will not exceed 10000.
2. Can the subdomains overlap or be the same across multiple entries in cpdomains?
   • Yes, subdomains can be the same across multiple entries, and their visit counts should be aggregated.
3. What should be the format of the output?
   • The output should be a list of strings, each formatted as “count domain”.

Strategy

1. Initialize a HashMap:
   • Use a HashMap to store the counts of each subdomain.
2. Iterate through cpdomains:
   • For each entry, split it into the count and the domain parts.
   • Split the domain by . to handle subdomains.
3. Update Counts for Each Subdomain:
   • Use the HashMap to accumulate the counts for each subdomain.
4. Format the Result:
   • Convert the HashMap entries back into the “count domain” format for the result.

Code

import java.util.*;

public class SubdomainVisitCount {
    public List<String> subdomainVisits(String[] cpdomains) {
        Map<String, Integer> domainCounts = new HashMap<>();
        
        for (String cpdomain : cpdomains) {
            String[] parts = cpdomain.split(" ");
            int count = Integer.parseInt(parts[0]);
            String domain = parts[1];
            
            String[] subdomains = domain.split("\\.");
            String currDomain = "";
            
            for (int i = subdomains.length - 1; i >= 0; i--) {
                currDomain = subdomains[i] + (currDomain.isEmpty() ? "" : "." + currDomain);
                domainCounts.put(currDomain, domainCounts.getOrDefault(currDomain, 0) + count);
            }
        }
        
        List<String> result = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : domainCounts.entrySet()) {
            result.add(entry.getValue() + " " + entry.getKey());
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        SubdomainVisitCount svc = new SubdomainVisitCount();
        String[] cpdomains = {"9001 discuss.leetcode.com"};
        System.out.println(svc.subdomainVisits(cpdomains));
    }
}

Time Complexity

• Time Complexity: O(N), where N is the total length of all domain strings in the input list cpdomains. This is because we iterate through each input once, and for each domain string, we process each of its subdomains.
• Space Complexity: O(N), for storing the counts of the subdomains in the HashMap and the resulting list.

This solution efficiently computes the visit counts for each subdomain and formats the results correctly.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?