Finding nodes with 0 or 1 parents - DFS or BFS

Question

I completed the following question but it seems a lot of space complexity.

Do you think is there a way to complete it with graph search or so?

Thanks for the comments.

Suppose we have some input data describing a graph of relationships between parents and children over multiple generations. The data is formatted as a list of (parent, child) pairs, where each individual is assigned a unique positive integer identifier.

For example, in this diagram, 3 is a child of 1 and 2, and 5 is a child of 4:

1   2    4   15
 \ /   / | \ /
  3   5  8  9
   \ / \     \
    6   7    11

Sample input/output (pseudodata):

parentChildPairs = [ (1, 3), (2, 3), (3, 6), (5, 6), (15, 9), (5, 7), (4, 5), (4, 8), (4, 9), (9, 11) ]

Write a function that takes this data as input and returns two collections: one containing all individuals with zero known parents, and one containing all individuals with exactly one known parent.

Output may be in any order:

findNodesWithZeroAndOneParents(parentChildPairs) => [
  [1, 2, 4, 15],       // Individuals with zero parents
  [5, 7, 8, 11]        // Individuals with exactly one parent
]

Complexity Analysis variables:

n: number of pairs in the input

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ParentChild2 {

    public static void main(String[] argv) {
        int[][] parentChildPairs = new int[][] {
                {1, 3}, {2, 3}, {3, 6}, {5, 6}, {15, 9}, {5, 7},
                {4, 5}, {4, 8}, {4, 9}, {9, 11}
        };

        List<List<Integer>> list = findNodesWithZeroAndOneParents(parentChildPairs);

            for(int i=0; i<list.size(); i++) {
            System.out.println(list.get(i));
        }

    }

    static List<List<Integer>> findNodesWithZeroAndOneParents(int[][] parentChildPairs){

        List<List<Integer>> result = new ArrayList<>();

        Map<Integer, Integer> childMap = new HashMap<>();
        Map<Integer, Integer> parentMap = new HashMap<>();


        for(int i=0;i<parentChildPairs.length; i++){

            if(!childMap.containsKey(parentChildPairs[i][1])){
                childMap.put(parentChildPairs[i][1], 1);
            } else{
                int value = childMap.get(parentChildPairs[i][1]);
                childMap.put(parentChildPairs[i][1], value + 1);
            }
        }

        for(int i=0;i<parentChildPairs.length;i++){

            if(!childMap.containsKey(parentChildPairs[i][0])){
                parentMap.put(parentChildPairs[i][0], 1);
            }
        }

        ArrayList<Integer> temp2 = new ArrayList<>();
        for( Map.Entry<Integer, Integer> entry: parentMap.entrySet()){

            if(entry.getValue() == 1){
                temp2.add(entry.getKey());
            }

        }
        result.add(temp2);

        ArrayList<Integer> temp = new ArrayList<>();
        for( Map.Entry<Integer, Integer> entry: childMap.entrySet()){

            if(entry.getValue() == 1){
                temp.add(entry.getKey());
            }

        }

        result.add(temp);

        return result;
    }


}

Answer 1

Your space complexity looks like it is proportional to n (O(n)? I'm unsure of the notation). That doesn't seem bad to me, and I don't think it can be improved (but don't take my word for it, I'm not at all an expert). However, let me try cleaning up your code a bit. It's well-formatted, but there are some minor things that can be improved.

• args is the convention in Java for the argument to the main method, not argv.
• You can leave out the new int[][] when initializing a variable.
• If you're iterating over every element of an Iterable or array in order, you can use a foreach loop to help you out.
• You've also left blank lines in your code where they're not necessary, e.g. after the start of each for loop and between two closing braces.
• You can inline result using List.of, but that may be more a matter of personal style.
• You could name temp2 and temp something more descriptive such as zeroParentNodes and oneParentNodes.
• value could be named numParents or something similar to indicate that it is the number of parents found so far.
• You could initialize parent and child variables instead of indexing into the pair each time.

One odd thing I noticed - you add keys from parentMap whose values are 1 to temp2, but parentMap only contains values that are 1. Why not use a Set instead?

Also, you don't need to iterate over parentChildPairs twice - just put the parentSet and childMap operations in a single loop, and remove from parentSet as necessary.

Furthermore, instead of iterating over childMap to find children with a single parent, you can maintain two separate sets of children with one parent and children with multiple parents from the very start.

We now have this. The space complexity seems to be the same, but at least it's clearer (at least to me).

static List<List<Integer>> findNodesWithZeroAndOneParents(int[][] parentChildPairs) {
    Set<Integer> zeroParentNodes = new HashSet<>();
    Set<Integer> oneParentNodes = new HashSet<>();
    Set<Integer> extraParentNodes = new HashSet<>();

    for (int[] parentChild : parentChildPairs) {
        int parent = parentChild[0];
        int child = parentChild[1];

        if (!oneParentNodes.contains(parent) && !extraParentNodes.contains(parent)) {
            zeroParentNodes.add(parent);
        }

        if (zeroParentNodes.contains(child)) {
            zeroParentNodes.remove(child);
            oneParentNodes.add(child);
        } else if (oneParentNodes.contains(child)) {
            oneParentNodes.remove(child);
            extraParentNodes.add(child);
        } else {
            oneParentNodes.add(child);
        }
    }

    return List.of(new ArrayList<>(zeroParentNodes), new ArrayList<>(oneParentNodes));
}

I'd also suggest making your own Pair class for the input and output, but I don't know if you can change the input/output format, and it won't help with the space complexity anyway.

As Eric Stein suggested in the comments, the second if inside the for loop can be written more succinctly taking advantage of Set#remove's returned value, but I fear it loses some clarity that way.

if (zeroParentNodes.remove(child)) {
    oneParentNodes.add(child);
} else if (oneParentNodes.remove(child)) {
    extraParentNodes.add(child);
} else {
    oneParentNodes.add(child);
}