Finding a Common Element of 4 Elements

Question

I have a map TreeMap<Integer, Set<Integer>> adjacencyLists and an integer set TreeSet<Integer> specialNodes.

The map represents adjacency lists of a graph.

I want to pick keys from adjacencyLists and find if there is a common adjacent of them in specialNodes.

Is there a way to do this efficiently?

Example:

adjacencyLists is as follows:

[1, [2 3 4 5]]
[2, [1 5]]  
[3, [1 4 5]]  
[4, [1 3]]  
[5, [1 2 3]]

and specalNodes is as follows:

[1 3 4 5]

In this example, 4 and 5 are present in the values of first and third entries of adjacencyLists.

Hence, writing a function findCommon(1,3) should give me [4 5]
Similarly, findCommon(1,5) should return null because '2' is the only element that is common and is not in specialNodes.

`findCommon(1,3)` gives `[4 5]`. So what is the use of `specialNodes`? — HelloWorld123456789, May 02 '14 at 14:38
They are `TreeSet`s. I assume that they are sorted. Nevertheless, I can sort them. It take `O(nlogn)` time. No problem. — padawan, May 02 '14 at 14:43
Yeap, I add the elements as `put(adjacencyLists.size(), set);` — padawan, May 02 '14 at 14:57

score 2 · Answer 1 · edited May 23 '17 at 12:29

2

Here's a step by step procedure.

Get the two values from the keys. O(logn).
Sort them. O(nlogn).
Find the common elements. O(m+n).
Search for the common elements in specialNodes. O(m+n).

Hence worst case time complexity = O(nlogn).

edited May 23 '17 at 12:29

Community

1
1

answered May 02 '14 at 14:47

HelloWorld123456789

5,299
3
23
33

score 1 · Accepted Answer · answered May 02 '14 at 14:31

So if I'm understanding correctly you already have a set for each Integer listing its adjacency?

The easiest efficient way I can see to do this is to make use of another Set. Sets are very fast for checking if they already contain values.

Set<Integer> adjacent = new HashSet<>();

for (Integer i: toCheck) {
   int oldCount = adjacent.size();
   Set<Integer> check = adjacencyLists.get(i);
   adjacent.addAll(check);
   if (adjacent.size() != oldCount+check.size()) {
      // Duplicate found
      return true;
   }
}
return false;

If you need to know the identify of the common then loop through doing individual add calls instead of doing the addAll and check each add for success. This may actually be more efficient as no need to do the size checks:

Set<Integer> adjacent = new HashSet<>();

for (Integer i: toCheck) {
   Set<Integer> check = adjacencyLists.get(i);
   for (Integer c: check)
      if (!adjacent.add(c)) {
         // Duplicate found
         return c;
      }
}
return null;

Just saw the request for the full list of common members:

Set<Integer> adjacent = new HashSet<>();
Set<Integer> results = new HashSet<>();

for (Integer i: toCheck) {
   Set<Integer> check = adjacencyLists.get(i);
   for (Integer c: check)
      if (!adjacent.add(c)) {
         // Duplicate found
         results.add(c);
      }
}
return results;

score 1 · Answer 3 · answered May 02 '14 at 14:32

Not 100% sure what you mean, but this is my idea. One possible way is to use a search algorithm like BFS. Since all those four nodes must have one common node, means if you use one of your four nodes as root and search for each other of the three nodes. If the search for all three is a successful they must have one common node.

score 0 · Answer 4 · answered May 02 '14 at 14:36

The obvious solution would be to make a copy of specialNodes, then call its method retainAll on all the sets that you are considering, and the resulting set contains the common nodes. Did you try it ? Is it not efficient enough ?

Code:

Set findCommons(int a, int b) {
    HashSet commonNodes = new HashSet(specialNodes);

    commonNodes.retainAll(adjacencyLists.get(a));
    commonNodes.retainAll(adjacencyLists.get(b));
    return commonNodes;
}

Finding a Common Element of 4 Elements

4 Answers4