Number of Comments per Post

easy hash map grouping count distinct

Problem

You are given a table of submissions where each row is either a post or a comment. A row is a post when its parent_id is null; otherwise it is a comment whose parent_id references the sub_id of a post. Rows may be duplicated. For every distinct post, report how many distinct comments it has. Posts with no comments report 0, and comments pointing to a parent that is not a post are ignored.

Inputrows = [(1,null), (2,null), (1,null), (12,null), (3,1), (5,2), (3,1), (4,1), (9,1), (10,2), (6,7)]

Output[(1, 3), (2, 2), (12, 0)]

Post 1 has distinct comments {3, 4, 9} → 3. Post 2 has {5, 10} → 2. Post 12 has none → 0. Comment 6 → 7 is dropped because 7 is not a post.

rows as sub_id:parent_id (parent blank = post), comma-separated

def comments_per_post(rows):
    posts = set()
    comments = {}
    for sub_id, parent_id in rows:
        if parent_id is None:
            posts.add(sub_id)
        else:
            comments.setdefault(parent_id, set()).add(sub_id)
    result = []
    for pid in sorted(posts):
        result.append((pid, len(comments.get(pid, set()))))
    return result

function commentsPerPost(rows) {
  const posts = new Set();
  const comments = new Map();
  for (const [subId, parentId] of rows) {
    if (parentId === null) {
      posts.add(subId);
    } else {
      if (!comments.has(parentId)) comments.set(parentId, new Set());
      comments.get(parentId).add(subId);
    }
  }
  const result = [];
  for (const pid of [...posts].sort((a, b) => a - b)) {
    const set = comments.get(pid);
    result.push([pid, set ? set.size : 0]);
  }
  return result;
}

List<int[]> commentsPerPost(int[][] rows) {
    TreeSet<Integer> posts = new TreeSet<>();
    Map<Integer, Set<Integer>> comments = new HashMap<>();
    for (int[] r : rows) {
        if (r[1] == Integer.MIN_VALUE) {       // null parent
            posts.add(r[0]);
        } else {
            comments.computeIfAbsent(r[1], k -> new HashSet<>()).add(r[0]);
        }
    }
    List<int[]> result = new ArrayList<>();
    for (int pid : posts) {
        Set<Integer> set = comments.get(pid);
        result.add(new int[]{ pid, set == null ? 0 : set.size() });
    }
    return result;
}

vector<pair<int,int>> commentsPerPost(vector<pair<int,int>>& rows) {
    set<int> posts;                              // sorted distinct posts
    unordered_map<int, set<int>> comments;        // parent -> distinct comment ids
    for (auto& r : rows) {
        if (r.second == INT_MIN) {               // null parent
            posts.insert(r.first);
        } else {
            comments[r.second].insert(r.first);
        }
    }
    vector<pair<int,int>> result;
    for (int pid : posts) {
        auto it = comments.find(pid);
        result.push_back({ pid, it == comments.end() ? 0 : (int)it->second.size() });
    }
    return result;
}

Explanation

Each row is either a post (its parent is null) or a comment pointing at a post via parent_id. Rows can repeat, so we must count distinct comments per post. Two collections handle this cleanly: a set of posts and a map comments from parent id to a set of comment ids.

In one pass we route every row: null parent goes into the posts set; otherwise we add the comment's id into comments[parent]. Using sets means duplicate rows collapse automatically — adding the same id twice changes nothing.

At the end we walk the posts in sorted order and report the size of that post's comment set, or 0 if it has none.

Example: post 1 collects comment ids {3, 4, 9} (the duplicate 3 is absorbed) → 3; post 2 collects {5, 10} → 2; post 12 has none → 0.

A comment whose parent is not a post (like 6 → 7) is stored in the map but never read, because we only iterate over real posts — so it is silently dropped.

Time: O(n log n) Space: O(n)