this has several answers but no need for dynamic programming solution. 1. sort + join - O(nlogn) 2. keep counts for integers in array or hashmap - O(n) but need lot of extra space O(n)

Seems the question is to give an array with the common elements between the two arrays. If this is the case, you should use a HashMap. The keys are numbers in the first array. The value is the number of times each one shows up. Have an array for the result. Then go over the second array. Look for each number in the hashMap. If it's there and the value is greater than 0, append it to the result and reduce in 1 the value in the hashmap for that number. public static Integer [] commonElements ( int [] a, int [] b ){ java.util.HashMap h = new java.util.HashMap (); for ( int e: a ){ if (h.containsKey(e))h.put(e, h.get(e)+1); else h.put(e, 1); } java.util.ArrayList resultAL = new java.util.ArrayList (); for ( int e: b){ if ( h.containsKey(e)&&h.get(e)>0){ resultAL.add(e); h.put(e, h.get(e)-1); } } Integer[] result = resultAL.toArray(new Integer [ 0 ]); return result; }

sort + join - looks like the answer

The question is confusing.You are sayin common sub array but the sub array is present only in 2nd array.

common sub array should be {2,3} instead of {2,2,3,3}

I try to an array as a hash table. index is the element, value is the times the element appears in arr1, and then traversal arr2, with the hash table. The problem of my algorithm is that I need to know the range of the arrays' element value, because I need to use that to define the size of my array. The interview asked me if I was familiar with the STL hashmap, which i was not

Was this asked in phone interview ?