Leetcode 1600: Throne Inheritance
In a kingdom, there is a well-defined hierarchy of inheritance, starting with the king. The inheritance order depends on the family’s birth and death events. Implement a class to keep track of the order, excluding the dead members.
Problem
Approach
Steps
Complexity
Input: An array of commands and their arguments representing actions like initializing the kingdom, adding a new child, marking someone deceased, or getting the inheritance order.
Example: ["king", "andy"]
Constraints:
• 1 <= kingName.length, parentName.length, childName.length, name.length <= 15
• All name arguments consist of lowercase English letters only.
• At most 105 calls will be made to birth and death.
• At most 10 calls will be made to getInheritanceOrder.
Output: The result of each getInheritanceOrder call is a list of members currently alive in the inheritance order, excluding any deceased individuals.
Example: ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
Constraints:
• The list should exclude dead members and maintain the birth order.
Goal: To maintain an efficient way of getting the current inheritance order and adjusting it based on births and deaths.
Steps:
• Initialize the king as the root of the inheritance tree.
• Use a family tree to represent the relationships between parents and children.
• For each birth, add a child to the parent's list.
• For each death, mark the person as deceased.
• For each getInheritanceOrder call, traverse the family tree and return the order of alive members.
Goal: The family tree should be traversed efficiently and the inheritance order should exclude deceased members.
Steps:
• The time complexity for each getInheritanceOrder call should be manageable given the constraints.
• The death method should not affect the recursive traversal of the family tree.
Assumptions:
• Each birth event adds a new member, and each death event removes one from the inheritance order.
• Input: ["king", "andy"]
• Explanation: After initializing with the king, Andy is born and added to the inheritance order.
Approach: To implement the ThroneInheritance class, we need to maintain a tree structure for the family and track the alive status of each member.
Observations:
• We need to efficiently manage births, deaths, and inheritance order retrieval.
• We can use a hashmap to represent the family tree and a set to track dead members.
Steps:
• Use a hashmap to store the family tree with parents as keys and children as values.
• Use a set to store deceased members.
• For each call to getInheritanceOrder, recursively traverse the family tree, skipping deceased members.
Empty Inputs:
• If no birth events are called, the inheritance order will only contain the king.
Large Inputs:
• The solution should efficiently handle up to 105 birth and death events.
Special Values:
• Ensure that deaths are handled without affecting the family tree structure.
Constraints:
• Make sure to handle all edge cases like multiple deaths in a row or no births.
unordered_map<string, vector<string>> family;
string root;
public:
ThroneInheritance(string kingName) {
root = kingName;
}
void birth(string parentName, string childName) {
family[parentName].push_back(childName); // Appending at the end takes care of oldest to youngest
}
void death(string name) {
dead[name] = true;
}
void dfs(vector<string> &ans, string root) {
if (!dead[root]) { // Just check if dead before inserting into the order.
ans.push_back(root);
}
for (string child: family[root]) {
dfs(ans, child);
}
}
vector<string> getInheritanceOrder() {
vector<string> ans;
dfs(ans, root);
return ans;
}
1 : Variable Initialization
unordered_map<string, vector<string>> family;
This initializes a 'family' map that associates a string (parent name) with a list of child names (vector of strings). This structure is used to represent the family tree.
2 : Variable Initialization
string root;
This initializes the 'root' variable as a string, which holds the name of the king (the root of the family tree).
3 : Access Control
public:
This indicates the beginning of the public section of the class, where methods are accessible from outside the class.
4 : Constructor
ThroneInheritance(string kingName) {
This is the constructor of the 'ThroneInheritance' class, which initializes the root of the family tree (the king) with the given 'kingName'.
5 : Constructor
root = kingName;
This assigns the 'kingName' to the 'root' variable, setting the initial king of the family tree.
6 : Method Definition
void birth(string parentName, string childName) {
This method is called when a new child is born, and it adds the child to the list of children under the given parent.
7 : Method Logic
family[parentName].push_back(childName); // Appending at the end takes care of oldest to youngest
This line adds the 'childName' to the list of children of the specified 'parentName'. The comment explains that the children are stored in order of birth, with the oldest child added first.
8 : Method Definition
void death(string name) {
This method marks a family member as deceased by setting their status in the 'dead' map.
9 : Method Logic
dead[name] = true;
This line updates the 'dead' map to mark the person with the name 'name' as deceased.
10 : Method Definition
void dfs(vector<string> &ans, string root) {
This method performs a depth-first search (DFS) to recursively traverse the family tree and collect the names of family members in the inheritance order.
11 : Method Logic
if (!dead[root]) { // Just check if dead before inserting into the order.
This checks whether the person is dead before adding them to the inheritance order. If they are not dead, their name is added to the list.
12 : Method Logic
ans.push_back(root);
If the person is not dead, their name ('root') is added to the 'ans' vector, which stores the inheritance order.
13 : Method Logic
for (string child: family[root]) {
This loops through all children of the current 'root' in the family tree, and recursively calls the 'dfs' method to process each child.
14 : Recursive Call
dfs(ans, child);
This makes a recursive call to the 'dfs' method for each child, ensuring the inheritance order is traversed.
15 : Method Definition
vector<string> getInheritanceOrder() {
This method returns a vector of strings that contains the inheritance order by calling the 'dfs' method.
16 : Method Logic
vector<string> ans;
This initializes a vector 'ans' to hold the final inheritance order.
17 : Method Logic
dfs(ans, root);
This calls the 'dfs' method to populate the 'ans' vector with the inheritance order starting from the 'root' (king).
18 : Method Logic
return ans;
This returns the populated 'ans' vector containing the inheritance order.
Best Case: O(1)
Average Case: O(n)
Worst Case: O(n)
Description: The worst-case time complexity for getInheritanceOrder is O(n), where n is the number of family members.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage of the family tree and dead members.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus