leetcode-algorithms/src/ThroneInheritance.java at master · anishLearnsToCode/leetcode-algorithms · GitHub

History

63 lines (52 loc) · 1.65 KB

Raw

// https://leetcode.com/problems/throne-inheritance

// N = people in royal family

// birth() T: O(1)

// death() T: O(1)

// getInheritanceOrder T: O(N)

// S: O(N)

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

public class ThroneInheritance {

private static final class Person {

private final String name;

private boolean isAlive = true;

private final List<Person> children = new ArrayList<>();

Person(String name) {

this.name = name;

}

void markDead() {

this.isAlive = false;

}

void addChild(Person child) {

this.children.add(child);

}

private final Map<String, Person> royalFamily = new HashMap<>();

private final Person king;

public ThroneInheritance(String kingName) {

king = new Person(kingName);

royalFamily.put(kingName, king);

}

public void birth(String parentName, String childName) {

Person child = new Person(childName);

royalFamily.put(childName, child);

royalFamily.get(parentName).addChild(child);

}

public void death(String name) {

royalFamily.get(name).markDead();

}

public List<String> getInheritanceOrder() {

final List<String> names = new ArrayList<>();

getInheritanceOrder(king, names);

return names;

}

public void getInheritanceOrder(Person person, List<String> names) {

if (person == null) return;

if (person.isAlive) names.add(person.name);

for (Person child : person.children) {

getInheritanceOrder(child, names);

}

leetcode-algorithms/src/ThroneInheritance.java at master · anishLearnsToCode/leetcode-algorithms · GitHub

Expand file tree

Breadcrumbs

ThroneInheritance.java

Latest commit

History

Breadcrumbs

ThroneInheritance.java

File metadata and controls