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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Subdomain Visit Count and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →