Leetcode 1600. Throne Inheritance

Problem Explanation

Let's understand this problem by dissecting it slightly. The Kingdom is a family tree that starts with the King, and each node in the tree is a person who at some point can have children who are the next nodes, also when a person dies it does not remove the person from the tree, it simply marks the person as dead. These actions form the context of the kingdom with births and deaths occurring.

In addition, each node can have multiple children but there's an order of precedence, which is by age, older siblings are higher on the succession line than younger siblings. In essence, the problem is about a recursive search through a tree with a specific condition determining the order of the search.

For instance, if we consider an example of a kingdom with the king as the only person initially:

  • We initialized a new ThroneInheritance object with the king's name, then the king had 3 children (Andy, Bob, and Catherine) in that order. Then,
    Andy also had a child (Matthew), Bob had two children (Alice and Asha). The order of inheritance then becomes: king->andy->Matthew->bob->Alice->Asha->catherine.

If Bob dies at this point, he is marked as dead and the new order of inheritance becomes: king->andy->Matthew->Alice->Asha->catherine However, if Bob is later alive, the order of inheritance changes back to the initial order.

Solution Approach

The solution approach to this problem can be approached by using Depth-First Search (DFS) algorithm in recursion. DFS algorithm is a traversal or search algorithm that uses a stack data structure to explore all the nodes by going forward if possible, else by backtracking. In addition, the structure of the family is modelled as a graph using unordered_map and unordered_set in C++. The inheritance order is obtained by doing a DFS on the family tree, excluding the dead.

Python

1
2python
3class ThroneInheritance:
4    def __init__(self, kingName: str):
5        self.king = kingName
6        self.dead = set()
7        self.children = defaultdict(list)
8
9    def birth(self, parentName: str, childName: str) -> None:
10        self.children[parentName].append(childName)
11
12    def death(self, name: str) -> None:
13        self.dead.add(name)
14
15    def getInheritanceOrder(self) -> List[str]:
16        res = []
17        def dfs(name): # Helper function for DFS traversal
18            if name not in self.dead:
19                res.append(name)
20            for child in self.children[name]:
21                dfs(child)
22        dfs(self.king) # Perform DFS from king
23        return res

Java

1
2java
3// Creating family as an adjacency list, marking death in a hash set. 
4// Get Inheritance order using DFS.
5class ThroneInheritance {
6    Map<String, List<String>> children = new HashMap<>();
7    Set<String> death = new HashSet<>();
8    String king;
9
10    public ThroneInheritance(String king) {
11        this.king = king;
12    }
13
14    public void birth(String parent, String child) {
15        children.computeIfAbsent(parent, k -> new ArrayList<>()).add(child);
16    }
17
18    public void death(String person) {
19        death.add(person);
20    }
21
22    public List<String> getInheritanceOrder() {
23        List<String> order = new ArrayList<>();
24        dfs(king, order);
25        return order;
26    }
27
28    private void dfs(String curr, List<String> order) {
29        if (!death.contains(curr))
30            order.add(curr);
31        for (String child : children.getOrDefault(curr, new ArrayList<>()))
32            dfs(child, order);
33    }
34}

JavaScript

1
2javascript
3class ThroneInheritance {
4    constructor(kingName) {
5        this.kingName = kingName
6        this.map = new Map
7        this.dead = new Set
8    }
9
10    birth(parentName, childName) {
11        if (!this.map.has(parentName)) this.map.set(parentName, [])
12        this.map.get(parentName).push(childName)
13    }
14
15    death(name) {
16        this.dead.add(name)
17    }
18
19    getInheritanceOrder() {
20        let res = []
21        this.dfs(this.kingName, res)
22        return res
23    }
24
25    dfs(curName, res) { // Helper function for DFS traversal
26        if (!this.dead.has(curName)) res.push(curName)
27        this.map.get(curName)?.map(childName => this.dfs(childName, res))
28    }
29}

C#

1
2csharp
3public class ThroneInheritance {
4    Dictionary<string, List<string>> map = new Dictionary<string, List<string>>();
5    HashSet<string> deads = new HashSet<string>();
6    string king;
7    public ThroneInheritance(string kingName) {
8        king =kingName;
9        map[king] = new List<string>();
10    }
11    
12    public void Birth(string parentName, string childName) {
13        map[parentName].Add(childName);
14        if (!map.ContainsKey(childName))
15        {
16            map[childName] = new List<string>();
17        }
18    }
19    
20    public void Death(string name) {
21        deads.Add(name);
22    }
23    
24    public IList<string> GetInheritanceOrder() {
25        var res = new List<string>();
26        dfs(map[king], res);
27        return res;
28    }
29    
30    private void dfs(List<string> child,string parent, List<string> res)
31    {
32        if(!deads.Contains(parent)) res.Add(parent);
33        foreach(var c in child){
34            dfs(map[c],c,res);
35        }
36    }
37}

C++

1
2cpp
3class ThroneInheritance {
4public:
5    string kingName;
6    unordered_map<string,vector<string>> family;
7    set<string> dead;
8    ThroneInheritance(string kingName) : kingName(kingName) {}
9
10    void birth(string parentName, string childName) {
11        family[parentName].push_back(childName);
12    }
13
14    void death(string name) {
15        dead.insert(name);
16    }
17
18    vector<string> getInheritanceOrder() {
19        vector<string> ans;
20        dfs(kingName, ans);
21        return ans;
22    }
23
24private:
25  
26    void dfs(const string& name, vector<string>& ans) {
27        if (!dead.count(name))
28            ans.push_back(name);
29        for (const string& child : family[name])
30            dfs(child, ans);
31    }
32};

Conclusion

For this specific problem, we apply a combination of graph theory and the Depth-First Search algorithm. This approach allows us to effectively model the inheritance structure of the kingdom and properly track any birth and death events. By using this method, we can efficiently retrieve the current inheritance line when needed.

When implementing this solution in different programming languages, it is important to be familiar with the relevant data structures and syntax. In the Python, Java, JavaScript, C# and C++ solutions above, we create data structures for the family tree represented as a graph and a set to track the current dead members of the community. These essential data structures make the implementation of DFS straightforward.

Each of the solutions provided performs the necessary operations required for this problem:

  • Initializing the object with the king's name.
  • Handling births in the kingdom: Whenever a child is born, we add that child to the family tree structure under the parent's name.
  • Handling deaths in the kingdom: When a person dies, we add that person to the list of dead members.
  • Getting the inheritance order: We employ DFS to traverse the family tree and return an ordered list of inheritors (ignoring the list of dead members while doing so).

By utilizing these optimal data structures and algorithms, we ensure that our solution is maintainable, efficient and reliable. The nuances might be different with each programming language due to syntax and built-in methods, but the core concepts remain constant. This makes the problem of tracking the inheritance line in a kingdom simple and efficient.

This demonstrates the power of using appropriate algorithms and data structures to solve complex problems. Therefore, improving your ability to choose and implement these strategies could significantly boost your problem-solving skills.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫