How to get common elements from three array list optimally?

Question

I have 3 arrays

int a[] = {1,3,7,6};
int b[] = {2,5,0,4};
int c[] = {11,23,71,6};

I want to find common elements from these three arrays optimaly. I am thinking to use 3 for loops to find common elements but this is not optimal .So is there any optimal better way of doing it rather than using nested for loop?

What is a "common element"? Is it one which appears in all three arrays? Or is it one which appears in any two of these arrays? When the latter, do you need to know in which two arrays this "common element" occurs or do you only need to know the duplicates? — Philipp, Jan 14 '22 at 15:09
Does this answer your question? [How do I get the intersection between two arrays as a new array?](https://stackoverflow.com/questions/13270491/how-do-i-get-the-intersection-between-two-arrays-as-a-new-array) — Sharon Ben Asher, Jan 14 '22 at 15:11
@SharonBenAsher It likely won't, because the question here is about 3 arrays. Adapting the answers from that question to more than two arrays isn't trivial. — Philipp, Jan 14 '22 at 15:13

Sharon Ben Asher · Answer 1 · 2022-01-14T15:27:56.673

This is the most concise solution, though I am not sure it is the most efficiant:

List<Integer> commonItems = new ArrayList<>(Arrays.asList(a));
commonItems.retainAll(Arrays.asList(b));
commonItems.retainAll(Arrays.asList(c));

JDK doc of List.retainAll:

Retains only the elements in this list that are contained in the specified collection (optional operation). In other words, removes from this list all of its elements that are not contained in the specified collection.

score 0 · Answer 2 · answered Jan 14 '22 at 15:25

0

You can use a Set for each array to store elements so that they can be accessed in O(1) time and then iterate over elements in any set and check if it's present in other two sets as well since set of common elements is guaranteed to be a subset of all the three sets.

    int a[] = {1,3,7,6};
    int b[] = {2,5,0,4};
    int c[] = {11,23,71,6};
    Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();
    Set<Integer> set3 = new HashSet<>();
    for(int x: a)
        set1.add(x);
    for(int x: b)
        set2.add(x);
    for(int x: c)
        set3.add(x);
    List<Integer> res = new ArrayList<>();
    Iterator<Integer> itr = set1.iterator();
    while(itr.hasNext()){
        int ele = itr.next();
        if(set2.contains(ele) && set3.contains(ele)){
            res.add(ele);
        }
    }
    return res;

This approach should also work in cases where an element is repeated in an array and thus can increase frequency of count if single hashmap based approach is used.

answered Jan 14 '22 at 15:25

Siddharth

73
8

It appears that your code only iterates through `set1` and doesn't use any of the advantages of `HashSet` on that particular collection. Why not just use the array `a` as-is? – Philipp Jan 14 '22 at 15:27
Checking the existence of an element in an array would be an O(n) operation while for a set/map it is O(1) amortized. – Siddharth Jan 14 '22 at 15:39
That's true, but your code does not check for existence in `set1`. You only do that in `set2` and `set3`. All your code does with `set1` is to iterate it, which is an `O(n)` operation in either data structure (but probably still slower in a HashSet). – Philipp Jan 14 '22 at 15:45
Although I can see the logic behind your statement and that is absolutely correct, we can use array a as is. But for writing cleaner and concise code for the statement we would be essentially creating set of the three arrays and use retainAll to get intersection of the three sets. This longish code better explains the workings though. – Siddharth Jan 14 '22 at 15:51
I don't see how this completely pointless conversion step makes the code easier to understand, but you do you. – Philipp Jan 14 '22 at 15:53

Shridutt Kothari · Answer 3 · 2022-01-14T15:24:31.780

Assuming the arrays are having unique elements in themself (no duplicates in an array)

You can use some data structure like HashMap to push all elements of the arrays as keys, and values as their count of occurrences to find common elements if the value is 3 :

private ArrayList<Integer> commonElements() {
        int a[] = {1,3,7,6};
        int b[] = {2,5,0,4};
        int c[] = {11,23,71,6};
        
        HashMap<Integer, Integer> elementCunt = new HashMap<>();
        
        for(int element: a) {
            if(elementCunt.containsKey(element)) {
                elementCunt.put(element, elementCunt.get(element) + 1);
            } else {
                elementCunt.put(element, 1);
            }
        }
        
        for(int element: b) {
            if(elementCunt.containsKey(element)) {
                elementCunt.put(element, elementCunt.get(element) + 1);
            } else {
                elementCunt.put(element, 1);
            }
        }
        
        for(int element: c) {
            if(elementCunt.containsKey(element)) {
                elementCunt.put(element, elementCunt.get(element) + 1);
            } else {
                elementCunt.put(element, 1);
            }
        }
        
        Iterator<Integer> itr = elementCunt.keySet().iterator();
        
        ArrayList<Integer> commonElements = new ArrayList<>();
        
        while(itr.hasNext()) {
            int key = itr.next();
            if(elementCunt.get(key) == 3) {
                commonElements.add(key);
            }
        }
        
        return commonElements;
    }

if assuming the arrays are having unique elements, how can they have common ones? — Sharon Ben Asher, Jan 14 '22 at 15:23
@SharonBenAsher assuming each array is having unique elemtens — Shridutt Kothari, Jan 14 '22 at 15:23

How to get common elements from three array list optimally?

3 Answers3