LeetCode 1600: Throne Inheritance Solution

Master LeetCode problem 1600 (Throne Inheritance), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1600. Throne Inheritance

Medium

Hash Table Tree Depth-First Search Design

Problem Explanation

Explanation:

To solve this problem, we can use a combination of a tree structure to represent the relationships in the kingdom and a list to maintain the order of inheritance excluding dead people.

Data Structures:
- We can represent the relationships in the kingdom using a tree structure where each person is a node with their children as their descendants.
- We can maintain the order of inheritance using a list where we append the names of people in the order they are born.
Algorithm:
- Initialize the tree with the king as the root node and an empty list for the inheritance order.
- Implement the birth function to add a child to a parent in the tree.
- Implement the death function to mark a person as dead in the tree.
- Implement the getInheritanceOrder function to return the current order of inheritance excluding dead people based on a preorder traversal of the tree.
Time Complexity:
- Initializing the kingdom: O(1)
- Adding a child: O(1)
- Marking a person as dead: O(1)
- Returning the inheritance order: O(n) where n is the number of living people in the kingdom
Space Complexity:
- Storing the relationships in the tree: O(n)
- Storing the order of inheritance: O(n)

Solution Code

class ThroneInheritance {
    Map<String, List<String>> tree;
    Set<String> dead;
    String king;

    public ThroneInheritance(String kingName) {
        tree = new HashMap<>();
        dead = new HashSet<>();
        king = kingName;
        tree.put(king, new ArrayList<>());
    }

    public void birth(String parentName, String childName) {
        tree.get(parentName).add(childName);
        tree.put(childName, new ArrayList<>());
    }

    public void death(String name) {
        dead.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> order = new ArrayList<>();
        dfs(king, order);
        return order;
    }

    private void dfs(String person, List<String> order) {
        if (!dead.contains(person)) {
            order.add(person);
        }
        for (String child : tree.get(person)) {
            dfs(child, order);
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1600 (Throne Inheritance)?

This page provides optimized solutions for LeetCode problem 1600 (Throne Inheritance) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1600 (Throne Inheritance)?

The time complexity for LeetCode 1600 (Throne Inheritance) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1600 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1600 in Java, C++, or Python.

Back to LeetCode Solutions