# AC solution using Java HashMap

• ``````public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i = 0; i < nums1.length; i++)
{
if(map.containsKey(nums1[i])) map.put(nums1[i], map.get(nums1[i])+1);
else map.put(nums1[i], 1);
}

for(int i = 0; i < nums2.length; i++)
{
if(map.containsKey(nums2[i]) && map.get(nums2[i]) > 0)
{
map.put(nums2[i], map.get(nums2[i])-1);
}
}

int[] r = new int[result.size()];
for(int i = 0; i < result.size(); i++)
{
r[i] = result.get(i);
}

return r;
}
}``````

• Same idea, Java 8 using `Stream`

``````        Map<Integer, Long> map = Arrays.stream(nums2).boxed().collect(Collectors.groupingBy(e->e, Collectors.counting()));
return Arrays.stream(nums1).filter(e ->{
if(!map.containsKey(e)) return false;
map.put(e, map.get(e) - 1);
if(map.get(e) == 0) map.remove(e);
return true;
}).toArray();``````

• the question is confusing until I saw this code. basically it is asking all common number including duplicate ones.

• ``````public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
List<Integer> res = new ArrayList<Integer>();
Arrays.sort(nums1);
Arrays.sort(nums2);
for(int i = 0, j = 0; i< nums1.length && j<nums2.length;){
if(nums1[i]<nums2[j]){
i++;
}
else if(nums1[i] == nums2[j]){
i++;
j++;
}
else{
j++;
}
}
int[] result = new int[res.size()];
for(int i = 0; i<res.size();i++){
result[i] = res.get(i);
}
return result;
}
}``````

• i agree with you !!!

• @junhong202 Same problem here, I was confused by the question itself.

• Probably nit picking here, but you can insert into a hash map more concisely by doing the following

``````for (int i = 0; i < nums1.length; i++) {
Integer prevVal = hash.get(nums1[i]);
hash.put(nums1[i], prevVal == null? 1 : prevVal +
}
``````

great solution! :)

• using stream

``````public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {

Map<Integer, Integer> map = new HashMap();
List<Integer> list = new ArrayList();
for (int n : nums1) {
map.put(n, map.getOrDefault(n, 0) + 1);
}

for (int n : nums2) {
Integer intersection = map.get(n);

if(intersection != null && intersection > 0) {
map.put(n, map.get(n) - 1);
}
}

return list.stream().mapToInt(i->i).toArray();
}
}
``````

• Instead of storing into ArrayList and then to array, initialize an array with length of nums2 or nums1, which one is lesser.

``````int[] result = new int[nums1.length];
int pos = 0;
``````

Do this inside the loop,

``````result[pos++] = val;
//Outside the loop, return the result with new length set.
return Arrays.copyOf(result, pos);
``````

• Using a List.
1.) Add Elements of nums1 array in a List l1.
2.) check if elements of nums2 array are in list l1.
3.) if l1 contains an element of nums2, add that element in list2(result list) and remove that element from l1.
4.) Convert this list l2 to array

``````public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
List<Integer> l1 =new ArrayList<Integer>();
List<Integer> l2 =new ArrayList<Integer>();
for(int i:nums1){
}
for(int j:nums2){
if(l1.contains(j)){
l1.remove((Integer)j);
}
}
int[] a=new int[l2.size()];
int count=0;
for(int k:l2){
a[count++]=k;
}
return a;
}
}
``````

• Use ArrayList and two poiters .

``````public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
ArrayList<Integer> arraylist = new ArrayList<Integer>();
Arrays.sort(nums1);
Arrays.sort(nums2);
int index1 = 0;
int index2 = 0;
while (index1 < nums1.length && index2 < nums2.length) {
if (nums1[index1] == nums2[index2]) {
index1++;
index2++;
} else if (nums1[index1] < nums2[index2]) {
index1++;
} else {
index2++;
}
}
for (int i = 0; i < arraylist.size(); i++) {
}
}
}
``````

• @chintant Code is elegant, but the `l1.remove((Integer)j);` would be O(n) time complexity which would lead to O(n^2) in term of the for loop

• @OpMaker Thanks

• Storing the smallest array in the map is more efficient. You can add this before creation the map

``````        if(nums1.length > nums2.length){
int[] tmp = nums2;
nums2=nums1;
nums1=tmp;
}
``````

• @RobertLee2015
good solution

• @VanillaCoke
Great solution without sorting two arrays, thank you! The solution using java hashmap has `O(m + n)` time complexity and `O(min(m, n))` space complexity. In theory, they are faster than sorted arrays in terms of time complexity, at the expense of extra space. However, tests show that the 1st solution(85.83%) > 2nd solution(67.33%) > your solution(48.29%). The difference between theory and practice may lie in the fact that the frequent get/put operations on HashMap and final for-loop to convert a List<Integer> to an int array.

Here are two other solutions based on sorted arrays:
(1) linear search : `O(n*log n + m*log m)` time complexity.

``````public int[] intersect(int[] nums1, int[] nums2) {
int[] res = nums1.length < nums2.length ? new int[nums1.length] : new int[nums2.length];
if (res.length == 0) {
return res;
}

Arrays.sort(nums1);
Arrays.sort(nums2);

int pt1 = 0;
int pt2 = 0;
int pt = 0;
while(pt1 < nums1.length && pt2 < nums2.length) {
int n1 = nums1[pt1];
int n2 = nums2[pt2];
if (n1 == n2) {
res[pt++] = n1;
pt1++;
pt2++;
} else if (n1 > n2) {
pt2++;
} else {
pt1++;
}
}
return Arrays.copyOfRange(res, 0, pt);
}
``````

(2) binary search : `O((m+n)log n)`
STEP 1: determine the frequency of one number in "nums1", `f1`
STEP 2: determine the frequency of the same number in "nums2", `f2`
STEP 3: add this number in result array for `min(f1, f2)` times.

``````public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
int[] res = new int[nums1.length];
if (res.length == 0) {
return res;
}

// binary search version
int i = 0;
int j = 0;
int freq1, freq2, freq, num, lower, upper;
int[] bound;
Arrays.sort(nums1);
Arrays.sort(nums2);
while (j < nums2.length) {
num = nums2[j];
// determine the frequency of the number in "nums1"
bound = searchRange(num, nums1);
upper = bound[1];
lower = bound[0];
if (upper != -1 && lower != -1) {
freq1 = upper - lower + 1;
// calculate the frequency of the number in "nums2"
for (freq2 = 1; j < nums2.length - 1 && nums2[j] == nums2[j + 1]; j++) freq2++;
// add the number multiple time to the result
freq = (freq1 > freq2) ? freq2 : freq1;
for (int k = 0; k < freq; k++) {
res[i++] = num;
}
}
j++;
}
return Arrays.copyOfRange(res, 0, i);
}

private int[] searchRange(int target, int[] a) {
int[] bound = new int[]{-1, -1};

if (a.length == 0) return bound;
// search lower bound
int low = 0;
int high = a.length -1;
while (low + 1 < high) {
int mid = low + (high - low) / 2;
if (a[mid] == target) {
high = mid;
} else if (a[mid] > target) {
high = mid;
} else {
low = mid;
}
}
if (a[low] == target) {
bound[0] = low;
} else if (a[high] == target) {
bound[0] = high;
} else {
return bound;
}
// search upper bound
low = 0;
high = a.length - 1;
while (low + 1 < high) {
int mid = low + (high - low) / 2;
if (a[mid] == target) {
low = mid;
} else if (a[mid] > target) {
high = mid;
} else {
low = mid;
}
}
if (a[high] == target) {
bound[1] = high;
} else if (a[low] == target) {
bound[1] = low;
}
return bound;
}
``````

• @ericxliu
Elegant and concise solution! Big God.

• @VanillaCoke yes,we are same,as I just use `ArrayList`:

``````public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
List<Integer> list=new ArrayList<>();
List<Integer> relt=new ArrayList<>();
for(Integer i:nums2){
if(list.contains(i)){
list.remove(list.indexOf(i));
}
}
int[] re=new int[relt.size()];
for(int i=0;i<relt.size();i++){
re[i]=relt.get(i);
}
return re;
}
}
``````

• @VanillaCoke Nice! Exactly the same as mine!

• Agree, the problem is confusing, doesn't intersection means the same continous sequence other than all the same elements?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.