Skip to main content

811. Subdomain Visit Count

medium

Aggregate visit counts across every parent subdomain — discuss.leetcode.com also credits leetcode.com and com. A hash-map tally over a small string-split is all this needs.

By Sam K., Founder, InterviewChamp.AI · Last verified

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'. 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. Given an array of count-paired domains cpdomains, return an array of count-paired domains of each subdomain in the input. You may return the answer in any order.

Constraints

  • 1 <= cpdomains.length <= 100
  • 1 <= cpdomains[i].length <= 100
  • cpdomains[i] follows either the 'repi d1i.d2i.d3i' format or the 'repi d1i.d2i' format.
  • repi is an integer in the range [1, 10^4].
  • d1i, d2i, and d3i consist of lowercase English letters.

Examples

Example 1

Input
cpdomains = ["9001 discuss.leetcode.com"]
Output
["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]

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"]

Example 3

Input
cpdomains = ["1 a.b.c"]
Output
["1 a.b.c","1 b.c","1 c"]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Split each entry into count and the domain string.

Hint 2

For every suffix that starts at a dot boundary, add count to that suffix's bucket in a hash map.

Hint 3

Build the output by joining each (count, domain) pair back with a space.

Solution approach

Reveal approach

Hash map tally. Iterate every entry. Split into the integer count and the dotted domain. Walk the domain right-to-left, or split on '.' and rejoin progressively from the right, producing every suffix (e.g. 'discuss.leetcode.com' -> 'discuss.leetcode.com', 'leetcode.com', 'com'). For each suffix add count to counts[suffix]. After the input is consumed, build the result list by joining counts[domain] + ' ' + domain. O(N * L) time where N is entry count and L is the max number of dots per entry (effectively constant). O(distinct subdomains) space.

Complexity

Time
O(N*L)
Space
O(N*L)

Related patterns

  • hash-map
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon
  • Microsoft

More Hash Tables practice problems

See all Hash Tables problems →