How for N arrays of the same size with integers in ascending order, how can I choose the numbers common to arrays?

Question

In an interview, I was asked an algorithmic question, and I would like to get the same thing as the SO members. The question was as follows:

For arrays with the same size N with integers in ascending order, how would you choose the numbers common to all N arrays.

At first, I thought about iterating over the elements, starting with the first array flowing down to the rest of the arrays. But then this will lead to N-nuclear iterations, if I am right. So, I came up with a solution to add an account to the card, saving the element as a key and value as a counter. So I believe that time complexity is just N. Next is the Java implementation of my approach

public static void main(String[] args) { int[] arr1 = { 1, 4, 6, 8,11,15 }; int[] arr2 = { 3, 4, 6, 9, 10,16 }; int[] arr3 = { 1, 4, 6, 13,15,16 }; System.out.println(commonNumbers(arr1, arr2, arr3)); } public static List<Integer> commonNumbers(int[] arr1, int[] arr2, int[] arr3) { Map<Integer, Integer>countMap = new HashMap<Integer, Integer>(); for(int element:arr1) { countMap.put(element, 1); } for(int element:arr2) { if(countMap.containsKey(element)) { countMap.put(element,countMap.get(element)+1); } } for(int element:arr3) { if(countMap.containsKey(element)) { countMap.put(element,countMap.get(element)+1); } } List<Integer>toReturn = new LinkedList<Integer>(); for(int key:countMap.keySet()) { int count = countMap.get(key); if(count==3)toReturn.add(key); } return toReturn; } 

I just did it for three arrays to see how it would work. The question is talking about N arrays, although I think it will be anyway.

My question is, is there a better approach to solving this problem taking into account time complexity?

Answer 1

Think of it as 3 lines. Although the values ​​are different, the “delete” (by increasing the index of the array) is the smallest. When they match, “delete” (and write down) the matches.

 int i1 = 0; int i2 = 0; int i3 = 0; while (i1 < array1.size && i2 < array2.size && i3 < array3.size) { int next1 = array1[i1]; int next2 = array2[i2]; int next3 = array3[i3]; if (next1 == next2 && next1 == next3) { recordMatch(next1); i1++; i2++; i3++; } else if (next1 < next2 && next1 < next3) { i1++; } else if (next2 < next1 && next2 < next3) { i2++; } else { i3++; } } 

It is easy to generalize to N arrays, although with a large N you want to somehow optimize the comparison (NPE "heap").

Answer 2

I think this can be solved with a single parallel iteration over N arrays and the N-element min-heap . On the heap, you must hold the current element from each of the N input arrays.

The idea is that at each step you move through the array whose element is at the top of the heap (i.e. the smallest).

You will need to determine when the heap is completely composed of the same values. This can be done at a constant time while you are tracking the largest item that you have added to the heap.

If each array contains M elements, the worst time complexity will be O(M*N*log(N)) , and this will require O(N) memory.

Answer 3

to try

 public static Set<Integer> commonNumbers(int[] arr1, int[] arr2, int[] arr3) { Set<Integer> s1 = createSet(arr1); Set<Integer> s2 = createSet(arr2); Set<Integer> s3 = createSet(arr3); s1.retainAll(s2); s1.retainAll(s3); return s1; } private static Set<Integer> createSet(int[] arr) { Set<Integer> s = new HashSet<Integer>(); for (int e : arr) { s.add(e); } return s; } 

Answer 4

This is how I learned to do this in the class of algorithms. Not sure if it is “better,” but it uses less memory and less overhead because it iterates right through the arrays, rather than creating the map first.

 public static List<Integer> commonNumbers(int[] arr1, int[] arr2, int[] arr3, ... , int[] arrN) { List<Integer>toReturn = new LinkedList<Integer>(); int len = arr1.length; int j = 0, k = 0, ... , counterN = 0; for (int i = 0; i < len; i++) { while (arr2[j] < arr1[i] && j < len) j++; while (arr3[k] < arr1[i] && k < len) k++; ... while (arrN[counterN] < arr1[i] && counterN < len) counterN++; if (arr1[i] == arr2[j] && arr2[j] == arr3[k] && ... && arr1[i] == arrN[counterN]) { toReturn.add(arr1[i]); } } return toReturn; } 

Answer 5

This can be resolved in O(M * N) , where M is the length of the arrays.

Let's see what happens for N = 2 , it will be the problem of crossing a sorted list that has a classic solution like merging that works in O(l1 + l2) . (l1 = length of the first array, l2 = length of the second array). (Learn more about Combine Algorithms .)

Now repeat the iteration of the algorithm N times in inductive matter. (for example, the i-th time we will have the i-th array and the result of the intersection of the previous step). This will lead to the general O(M * N) algorithm.

You may also notice that the upper bound of the worst case is the best attainable, since all numbers must be considered for any valid algorithm. Thus, a deterministic algorithm with a stiffer upper bound cannot be created.

Answer 6

Ok - maybe a little naive here, but I think the hint is that the arrays are in ascending order. My Java is rusty, but here are some pseduocode. I have not tested it, so it is probably not perfect, but this should be a quick way to do this:

 I = 1 J = 1 K = 1 While I <= Array1Count and J <= Array2Count and K <= Array3Count If Array1(I) = Array2(J) If Array1(I) = Array3(K) === Found Match I++ J++ K++ else if Array1(I) < Array3(K) I++ end if end if else If Array1(I) < Array2(J) I++ else if Array2(J) < Array3(K) J++ else K++ end if end if end if Wend 

This is the base of Option 1 - you will have to transcode to make base base 0 (for example, Java and other languages)

Answer 7

I think another approach is to do the same with what we do at Mergesort: scan all arrays at once, getting the same numbers. This would allow using the fact that the arrays are sorted in order and would not use the extra space except the output array. If you just need to print the dormitory rooms, the extra space is not used.

 public static List<Integer> commonNumbers(int[] arrA, int[] arrB, int[] arrC) { int[] idx = {0, 0, 0}; while (idxA<arrA.length && idxB<arrB.length && idxC<arrC.length) { if ( arrA[idx[0]]==arrB[idx[1]] && arrB[idx[1]]==arrC[idx[2]] ) { // Same number System.out.print("Common number %d\n", arrA[idx[0]]); for (int i=0;i<3;i++) idx[i]++; } else { // Increase the index of the lowest number int idxLowest = 0; int nLowest = arrA[idx[0]]; if (arrB[idx[1]] < nLowest) { idxLowest = 1; nLowest = arrB[idx[1]]; } if (arrC[idx[2]] < nLowest) { idxLowest = 2; } idx[idxLowest]++; } } } 

To make this more general, you might want to take arrays of ints arrays, this will allow you to make the code prettier. Identical arrays must be stored in the array, otherwise it is difficult to code the "increment the index, which indicates the lowest number" code.

Answer 8

Your solution is acceptable, but it uses the NxM space. You can do this with O (N) space (where N is the number of arrays) or in O (1) space.

Decision No. 1 (Luigi Mendoza)

Assuming there are many small arrays (M <N), this may be useful, which results in O (M * N * Log M) time and constant space (excluding the output list).

Decision number 2

Scan arrays in ascending order, maintaining a minimum heap of size N containing the last visited values ​​(and indexes) of the arrays. Whenever the heap contains N copies of the same value, add the value to the output collection. Otherwise, delete the min value and go to the corresponding list.

The temporary complexity of this solution is O (M * N * Log N)

Answer 9

 public static List<Integer> getCommon(List<List<Integer>> list){ Map<Integer, Integer> map = new HashMap<Integer, Integer>(); int c=0; for (List<Integer> is : list) { c++; for (int i : is) { if(map.containsKey(i)){ map.put(i, map.get(i)+1); }else{ map.put(i, 1); } } } List<Integer>toReturn = new LinkedList<Integer>(); for(int key:map.keySet()) { int count = map.get(key); if(count==c)toReturn.add(key); } return toReturn; }