for above.. O(n log n) + O(n) * O(log n)

Two possible approaches: 1. Sort both arrays and then walk over each array simultaneously until you find all the common entries. This is O(n*logn) to do the sort and then walking over the items is O(n). 2. Walk over first array and insert each item into a hash table. Then search for each item in the hash table. This is O(n) time and O(n) space. If you're doing this a lot with the same sets of data, both algorithms allow you to do the expensive step once for each array and then find the common items in linear time.

Simple O(n) solution: public static Integer[] getIntersection(Integer[] a, Integer[] b) { Map countsMap = new HashMap(); for(Integer num : a) { // O(n) time countsMap.merge(num, 1, (x, y) -> y + 1); } List intersection = new LinkedList(); for(Integer num : b) { // O(n) time if(countsMap.containsKey(num)) { // O(1) int count = countsMap.get(num); // O(1) if(count > 0) { intersection.add(num); // O(1) countsMap.put(num, count - 1); // O(1) } } } // Above loops run in O(n) time each. // Total time complexity = O(2n) return intersection.toArray(new Integer[intersection.size()]); }

Actually, even conversion of list to array happens in O(n) time. So above solution required O(3n) and not O(2n), Please pardon my mistake.

given arrays of lengths n and m. A simple solution is to sort array n in O(n lg n) and for each item in array m, look for it in sorted n, O(m lg n). So total time = O((m+n)lg n), let array n be the short array. I feel there is a much quicker solution, maybe O(n+m) if we assume integers.

I have a O(n) algorithm: 1. Iterate over all the elements of first array a[] and build a dictionary mapping the element value to the index - O(n) 2. Now iterate over all the elements of the second array b[] and for each element that is already present in the dictionary, move the element to a different array that maintains the intersection elements - O(n) 3. Hence the overall complexity is O(n) in time and O(n) for the dictionary and the array to maintain the intersection elements.

Algorithm and pseudo code