1600. Throne Inheritance

MediumTreeDepth-First SearchDesignHash Table

Problem Description

In the realm of a kingdom, we have a continuous line of succession from the king down to the various members of the royal family. This order of inheritance begins with the king and is followed by his children, grandchildren, and so on, in order of their ages. The problem involves managing this order of inheritance, taking into account the birth of new royal members and the death of existing ones. The challenge is to maintain a dynamic list of the succession line, which can change when a new child is born or when someone dies.

Intuition

The primary approach to solving this problem involves simulating the family tree structure with appropriate data structures and then conducting depth-first search (DFS) traversals to generate the current order of inheritance.

Let's break down the solution into the following parts:

Data Structure: We need to efficiently represent the family tree to allow for the addition of new children (via births) and to keep track of deaths. We use a graph represented by a dictionary (self.g) where every person is a key, and their children form a list (the values).
Births: When a child is born, we add the child to the graph by appending the child's name to the parent's list in the dictionary. This operation corresponds to adding edges to the family tree graph.
Deaths: We keep track of deaths in a set (self.dead). We don't remove the person from the graph because their children still need to be in the inheritance order.
Order of Inheritance: To find the current inheritance order, we use DFS starting from the king. In this traversal, we add a person to the current order only if they are not marked as dead. Through DFS, the children of each person are visited in the order they were added, maintaining the age-based priority.
Exclusion of Dead People: Since we want the order to contain only living members, we check the set of dead people during DFS and only include those who are not in this set.

By following this approach, we can dynamically adjust the inheritance order as births and deaths are recorded, thus maintaining an up-to-date succession line.

Learn more about Tree and Depth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The solution to the inheritance problem is built around several key concepts in computer science, namely data structures, depth-first search, and class design.

Let's dive into each of these points:

Data Structures: We create three main attributes within the ThroneInheritance class:
- A graph self.g, represented as a dictionary, which captures the parent-child relationships.
- A set self.dead to keep track of the deceased family members.
- A variable self.king to store the name of the king, which is the root of our graph.
Class Methods: Three methods alter the state of the inheritance line:
- birth receives a parent name and a child name. The child's name is appended to the parent's list of children in the graph.
- death marks a family member as deceased by adding their name to the self.dead set.
- getInheritanceOrder invokes a DFS traversal method to calculate the current inheritance order.
Depth-First Search (DFS): We perform a DFS starting from the king every time getInheritanceOrder is called. Here's the breakdown of the DFS method used:
- A helper function dfs is defined within getInheritanceOrder for recursive traversal.
- Each time the DFS visits a person, it checks if they are alive (not in self.dead). If so, the person is added to the ans list, which represents the current inheritance order.
- The DFS continues recursively through the children (in the order they were added to self.g), ensuring the age-based succession is preserved.

This implementation allows us to efficiently manage the order of inheritance dynamically as births add to the self.g graph and deaths are recorded in self.dead. The getInheritanceOrder function can be called at any time to provide a snapshot of the living members in the line of succession, excluding those that have passed away.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

[1, 2, 3, 4, 5][1, 3, 6, 10, 15][15, 14, 12, 9, 5][5, 4, 3, 2, 1]

I don’t know

Example Walkthrough

Consider a kingdom with the following initial succession line: King (George), his children: oldest (John), and middle (Liam), and youngest (Claire).

In this structure, we have:

King George at the root.
John, Liam, and Claire as the children of George, listed in the order of their ages.

Let's set up the ThroneInheritance at this point:

self.g = { "George": ["John", "Liam", "Claire"] }
self.dead = set()
self.king = "George"

Now let's walk through a series of events and how the data structures would change:

Event 1: John has a child named William.

We execute the birth method for John and William.
self.g becomes { "George": ["John", "Liam", "Claire"], "John": ["William"] }.

Event 2: Claire gives birth to a child named Emma.

We call the birth method for Claire and Emma.
self.g is updated to { "George": ["John", "Liam", "Claire"], "John": ["William"], "Claire": ["Emma"] }.

Event 3: Liam passes away.

death method is called for Liam; so Liam is added to self.dead.
self.dead becomes { "Liam" }.
Note that Liam is not removed from self.g because it will affect the children's structure (if he had any).

Current Inheritance Order: At this time, if we call getInheritanceOrder, the DFS would start from George, move to John (as he is the oldest child), and then to William (child of John), skip Liam because he is in the self.dead set, and continue with Claire, and then Emma.

DFS order: George -> John -> William -> Liam (skipped, he's deceased) -> Claire -> Emma
The ans list would be ["George", "John", "William", "Claire", "Emma"].

This way, we can see how the dynamic list of succession maintains the correct order throughout the births and deaths within the royal family, representing the living members in the correct order of precedence at all times.

Solution Implementation

1from collections import defaultdict
2from typing import List
3
4class ThroneInheritance:
5    def __init__(self, king_name: str):
6        # Initialize a graph to represent the family tree
7        self.family_tree = defaultdict(list)
8
9        # Set to keep track of the deceased individuals
10        self.deceased = set()
11
12        # Store the king's name
13        self.king = king_name
14
15    def birth(self, parent_name: str, child_name: str) -> None:
16        # Add a child under the parent in the family tree
17        self.family_tree[parent_name].append(child_name)
18
19    def death(self, name: str) -> None:
20        # Mark a family member as deceased
21        self.deceased.add(name)
22
23    def get_inheritance_order(self) -> List[str]:
24        # Helper function to perform depth-first search (DFS)
25        def dfs(current_member):
26            # Append the current member to the order if they are not deceased
27            if current_member not in self.deceased:
28                order.append(current_member)
29            # Continue DFS for each child of the current member
30            for child in self.family_tree[current_member]:
31                dfs(child)
32
33        # List to store the current order of inheritance
34        order = []
35        # Start DFS from the king
36        dfs(self.king)
37        # Return the inheritance order
38        return order
39
40# Example of using the ThroneInheritance class
41# throne_inheritance = ThroneInheritance("King")
42# throne_inheritance.birth("King", "Andy")
43# throne_inheritance.death("King")
44# inheritance_order = throne_inheritance.get_inheritance_order()
45

1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.HashMap;
4import java.util.HashSet;
5import java.util.List;
6import java.util.Map;
7import java.util.Set;
8
9class ThroneInheritance {
10
11    // Graph to hold the family tree, where each key is a parent and the value is a list of children
12    private Map<String, List<String>> familyTree = new HashMap<>();
13
14    // Set to hold all the deceased family members
15    private Set<String> deceasedMembers = new HashSet<>();
16
17    // List to hold the order of inheritance
18    private List<String> inheritanceOrder;
19
20    // The name of the reigning king or the root of the family tree
21    private String king;
22
23    // Constructor initializes the ThroneInheritance with the name of the king
24    public ThroneInheritance(String kingName) {
25        king = kingName;
26    }
27
28    // Method to record the birth of a child, assigning the child to a parent in the family tree
29    public void birth(String parentName, String childName) {
30        familyTree.computeIfAbsent(parentName, k -> new ArrayList<>()).add(childName);
31    }
32
33    // Method to record the death of a family member by adding them to the set of deceased members
34    public void death(String name) {
35        deceasedMembers.add(name);
36    }
37
38    // Method to return the current order of inheritance, skipping deceased members
39    public List<String> getInheritanceOrder() {
40        inheritanceOrder = new ArrayList<>();
41        // Start the Depth-First-Search with the king
42        dfs(king);
43        return inheritanceOrder;
44    }
45
46    // Helper method to perform a Depth-First Search on the family tree starting from a given family member
47    private void dfs(String currentMember) {
48        // If the current member is not deceased, add them to the inheritance order
49        if (!deceasedMembers.contains(currentMember)) {
50            inheritanceOrder.add(currentMember);
51        }
52        // Recurse on all children of the current member
53        for (String child : familyTree.getOrDefault(currentMember, Collections.emptyList())) {
54            dfs(child);
55        }
56    }
57}
58
59// Usage example:
60// ThroneInheritance inheritance = new ThroneInheritance("king");
61// inheritance.birth("king", "andy");
62// inheritance.birth("king", "bob");
63// inheritance.birth("andy", "matthew");
64// inheritance.death("bob");
65// List<String> order = inheritance.getInheritanceOrder(); // Gets the inheritance order
66

1#include <string>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5using namespace std;
6
7class ThroneInheritance {
8private:
9    unordered_map<string, vector<string>> familyTree; // Holds the family tree as an adjacency list
10    unordered_set<string> deceased; // Keeps track of deceased family members
11    string monarch; // The name of the current king or queen
12    vector<string> inheritanceOrder; // Used to store the computed inheritance order
13
14public:
15    // Constructor initializes the family tree with the reigning monarch.
16    ThroneInheritance(string kingName) : monarch(kingName) {}
17
18    // Function to record the birth of a child
19    // parentName: The parent's name in the family tree
20    // childName: The child's name to be added under the parent
21    void birth(string parentName, string childName) {
22        familyTree[parentName].push_back(childName);
23    }
24
25    // Function to record the death of a family member
26    // name: The name of the deceased member
27    void death(string name) {
28        deceased.insert(name); // Add the member to the deceased set
29    }
30
31    // Function to get the current order of inheritance which represents the
32    // line of succession to the throne; filters out deceased members.
33    vector<string> getInheritanceOrder() {
34        inheritanceOrder.clear(); // Clear the previous order
35        depthFirstSearch(monarch); // Recursively compute the order starting from the monarch
36        return inheritanceOrder; // Return the computed order
37    }
38
39    // Helper function that performs a depth-first search on the family tree
40    // starting from the given family member to determine the line of succession.
41    void depthFirstSearch(const string& name) {
42        if (!deceased.count(name)) {
43            inheritanceOrder.push_back(name);
44        }
45        for (const auto& child : familyTree[name]) {
46            depthFirstSearch(child);
47        }
48    }
49};
50
51/**
52 * Example of using the ThroneInheritance class:
53 * 
54 * ThroneInheritance* obj = new ThroneInheritance(kingName);
55 * obj->birth(parentName, childName);
56 * obj->death(name);
57 * vector<string> order = obj->getInheritanceOrder();
58 * delete obj; // Don't forget to free allocated memory.
59 */
60

1// Define an adjacency list to hold the family tree where each parent maps to a list of children
2const familyTree: Record<string, string[]> = {};
3
4// Store the set of deceased family members
5const deceased: Set<string> = new Set();
6
7// The name of the current monarch
8let monarch: string;
9
10// Array to store the computed inheritance order
11let inheritanceOrder: string[] = [];
12
13// Initializes the family tree with the reigning monarch
14function initializeThroneInheritance(kingName: string) {
15    monarch = kingName;
16}
17
18// Records the birth of a child
19function birth(parentName: string, childName: string) {
20    if (!familyTree[parentName]) {
21        familyTree[parentName] = [];
22    }
23    familyTree[parentName].push(childName);
24}
25
26// Records the death of a family member
27function death(name: string) {
28    deceased.add(name); // Add the member to the deceased set
29}
30
31// Gets the current order of inheritance, representing the line of succession to the throne
32// Filters out deceased members
33function getInheritanceOrder(): string[] {
34    inheritanceOrder = []; // Clear the previous order
35    depthFirstSearch(monarch); // Recursively compute the order starting from the monarch
36    return inheritanceOrder;
37}
38
39// Performs a depth-first search on the family tree from the given family member
40// to determine the line of succession
41function depthFirstSearch(name: string) {
42    if (!deceased.has(name)) { // If the person is not deceased, add to the inheritance order
43        inheritanceOrder.push(name);
44    }
45    const children = familyTree[name] || []; // Get the children or an empty array if there are none
46    for (const child of children) {
47        depthFirstSearch(child); // Recursively search for each child
48    }
49}
50
51// Examples of using the above global functions and variables:
52// initializeThroneInheritance('King');
53// birth('King', 'Andy');
54// birth('King', 'Bob');
55// birth('Andy', 'Matthew');
56// birth('Bob', 'Alex');
57// birth('Bob', 'Asha');
58// death('Bob');
59// console.log(getInheritanceOrder());
60

Not Sure What to Study? Take the 2-min Quiz：

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Time and Space Complexity

`init` method

The __init__ method has a time complexity of O(1) as it simply initializes the data structures: a graph (self.g as a defaultdict of lists), a set (self.dead), and assigns the self.king variable . The space complexity of the __init__ method is also O(1) assuming the input kingName size does not contribute to the space complexity as it's a single value.

`birth` method

The birth method has a time complexity of O(1) as it just appends the child to the parent's children list in the graph. The space complexity is O(1) as well because it just adds one more element to the existing data structure.

`death` method

The death method has a time complexity of O(1) as it adds a name to the self.dead set. The space complexity is O(1) due to a single insertion into the set.

`getInheritanceOrder` method

The getInheritanceOrder method has a time complexity of O(N) where N is the total number of people in the inheritance order (both alive and dead). This is because it performs a depth-first search (DFS) over the entire family tree, visiting each person once. The space complexity of the getInheritanceOrder method can be considered to be O(N) for the DFS recursion stack in the worst case (assuming the family tree is heavily unbalanced and resembles a linked list), plus O(N) for the ans list where N is the number of alive people. So, the total space complexity is O(N).

Overall, the main performance concern in the code is related to how the DFS might behave on a very unbalanced family tree — in that case, the recursion could be a problem, and iterative approaches might need to be considered to keep the stack depth under control.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1600. Throne Inheritance

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

__init__ method

birth method

death method

getInheritanceOrder method

`init` method

`birth` method

`death` method

`getInheritanceOrder` method