People with Zero or One Parent
Problem statement
You are given data about parents and children. Each entry of parentChildPairs is [parent, child], and every person has a unique integer ID. A person can have any number of parents in the data.
Consider every person who appears in parentChildPairs, as a parent, as a child, or both. Return two lists:
- The people with zero parents in the data.
- The people with exactly one parent in the data.
Return them as [zeroParents, oneParent], each sorted in increasing order. A list with nobody in it is empty.
Function
parentGroups(parentChildPairs: int[][]) → int[][]Examples
Example 1
parentChildPairs = [[10,2],[11,2],[2,7],[12,7],[12,9],[9,4]]return = [[10,11,12],[4,9]]Nobody lists 10, 11 or 12 as a child, so they have zero parents. 9 has the single parent 12, and 4 has the single parent 9. 2 has two parents (10 and 11), and so does 7 (2 and 12), so they are in neither list.
Example 2
parentChildPairs = [[3,1],[4,1]]return = [[3,4],[]]3 and 4 have no parents. 1 has two parents, so nobody has exactly one parent and the second list is empty.
Example 3
parentChildPairs = [[5,8],[8,6]]return = [[5],[6,8]]5 has no parent. 8 has the single parent 5, and 6 has the single parent 8. Each list is in increasing order, so 6 comes before 8.
Constraints
1 <= parentChildPairs.length <= 2000parentChildPairs[i].length == 21 <= parentChildPairs[i][j] <= 10^5parentChildPairs[i][0] != parentChildPairs[i][1], and no pair appears twice.- The pairs have no cycle: nobody is their own ancestor.