1
\$\begingroup\$

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;
    }


}
\$\endgroup\$
2
  • \$\begingroup\$ Can the number of nodes in the graph be taken as a parameter? Are the nodes always going to be labelled 1..n, where n is the number of nodes? \$\endgroup\$
    – user
    Jul 22, 2021 at 17:31
  • \$\begingroup\$ This looks like the space complexity is proportional to n, what's wrong with it? \$\endgroup\$
    – user
    Jul 22, 2021 at 18:17

1 Answer 1

1
\$\begingroup\$

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);
}
\$\endgroup\$
5
  • \$\begingroup\$ This can be further improved by leveraging the fact that Set#remove() returns a boolean to get rid of the contains() checks. \$\endgroup\$
    – Eric Stein
    Jul 23, 2021 at 2:01
  • \$\begingroup\$ @user thanks for the more concise solution \$\endgroup\$ Jul 23, 2021 at 10:51
  • \$\begingroup\$ I am looking for a BFS solution, is there any solution ideas for these? \$\endgroup\$ Jul 23, 2021 at 10:51
  • \$\begingroup\$ @EricStein I’m afraid the code will become unclear if I do that, even if it will be concise. Thanks for the suggestion though, I’ll add it to my answer once I’m on my laptop. \$\endgroup\$
    – user
    Jul 23, 2021 at 12:07
  • \$\begingroup\$ @NeslihanBozer If you’re not taking some kind of graph object as input, I don’t see how DFS or BFS could help. It seems to me you’ll first have to construct a Map or some such object representing a graph and then find nodes with 0/1 parents, which will just take up more space. \$\endgroup\$
    – user
    Jul 23, 2021 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.