Exclude Cat- or Dog-Related Comments and All Their Replies by Reader Mode

You are given the comments of a discussion thread. Every comment either replies to another comment, its parent, or is top-level, so the comments form one or more trees. Each comment carries two flags that say whether it is about cats and whether it is about dogs.

A reader chooses one of two modes:

• "CAT_PERSON": does not want to see dog-related comments.
• "DOG_PERSON": does not want to see cat-related comments.

If a comment is about the reader's undesired animal, that comment and all of its replies, at every depth, must be excluded. Return the IDs of every excluded comment.

Follow-up: state the time and space complexity of your solution in terms of the number of comments.

Function Signature

def get_comments_to_exclude(comments: list[dict], mode: str) -> list[int]:

Each element of comments is a record with these keys:

Key	Type	Meaning
id	int	Unique comment ID
parent_comment	int or None	ID of the comment this one replies to, or None for a top-level comment
body	str	Comment text
cat	bool	Whether the comment is about cats
dog	bool	Whether the comment is about dogs

The records are the values of an ID-to-comment dictionary, supplied as a list in arbitrary order; a reply may appear before its parent.

Rules

• In "CAT_PERSON" mode a comment is undesired when dog is True; in "DOG_PERSON" mode, when cat is True. A comment with both flags set is undesired in both modes.
• A comment is excluded when it is undesired or when any of its ancestors (its parent, its parent's parent, and so on) is undesired. Once an ancestor is undesired, the comment's own flags do not matter.
• parent_comment may refer to an ID that does not appear in comments. Such a comment is treated as top-level: the missing parent causes no exclusion.
• body never affects the result.
• Return the excluded IDs in ascending order, without duplicates. Return [] when nothing is excluded.

Constraints

• 0 <= len(comments) <= 100000
• IDs are distinct integers with 0 <= id <= 10^9.
• parent_comment is None or an integer in the same range, never equal to the comment's own id, and following parent links never forms a cycle.
• A reply chain can be as deep as the total number of comments.
• mode is exactly "CAT_PERSON" or "DOG_PERSON".

Examples

Example 1

Input:
comments = [
  {"id": 0, "parent_comment": None, "body": "Look! A cute baby elephant taking a nap!", "cat": False, "dog": False},
  {"id": 2, "parent_comment": 1, "body": "I agree!", "cat": False, "dog": False},
  {"id": 11, "parent_comment": 0, "body": "Almost as cute as my poodle!", "cat": False, "dog": True}
]
mode = "CAT_PERSON"
Output: [11]

Comment 11 is about dogs and has no replies. Comment 2 replies to ID 1, which is not in the input, so it is treated as top-level and kept. In "DOG_PERSON" mode the output would be [].

Example 2

Input:
comments = [
  {"id": 5, "parent_comment": None, "body": "My puppy learned to sit today", "cat": False, "dog": True},
  {"id": 6, "parent_comment": 5, "body": "Congratulations!", "cat": False, "dog": False},
  {"id": 7, "parent_comment": 6, "body": "Thanks!", "cat": False, "dog": False},
  {"id": 8, "parent_comment": 7, "body": "Any training tips?", "cat": False, "dog": False},
  {"id": 9, "parent_comment": None, "body": "My cat ignores every command", "cat": True, "dog": False}
]
mode = "CAT_PERSON"
Output: [5, 6, 7, 8]

The tree is 5, then 6, then 7, then 8. Comment 5 is about dogs, so it and all its descendants are excluded, even though 6, 7 and 8 carry no flags. In "DOG_PERSON" mode the output would be [9].

Example 3

Input:
comments = [
  {"id": 6, "parent_comment": 5, "body": "Same here", "cat": False, "dog": False},
  {"id": 3, "parent_comment": 2, "body": "My dog does that too", "cat": False, "dog": True},
  {"id": 1, "parent_comment": None, "body": "What do your pets do all day?", "cat": False, "dog": False},
  {"id": 5, "parent_comment": 4, "body": "My cat and my dog nap together", "cat": True, "dog": True},
  {"id": 2, "parent_comment": 1, "body": "My cat sleeps on the keyboard", "cat": True, "dog": False},
  {"id": 4, "parent_comment": 1, "body": "Mostly sleeping, I assume", "cat": False, "dog": False}
]
mode = "DOG_PERSON"
Output: [2, 3, 5, 6]

Comments 2 and 5 are about cats. Comment 3 is about dogs, which this reader wants to see, but it is still excluded because its parent 2 is excluded; comment 6 is excluded as a reply to 5. In "CAT_PERSON" mode the output would be [3, 5, 6].