Solution
Approach 1: Two Sets
Intuition
The naive approach would be to iterate along the first array nums1
and to check for each value if this value in nums2
or not.
If yes  add the value to output. Such an approach would result
in a pretty bad
time complexity, where n
and m
are
arrays' lengths.
To solve the problem in linear time, let's use the structure
set
, which providesin/contains
operation in time in average case.
The idea is to convert both arrays into sets, and then iterate over the smallest set checking the presence of each element in the larger set. Time complexity of this approach is in the average case.
!?!../Documents/349_LIS.json:1000,352!?!
Implementation
Complexity Analysis

Time complexity : , where
n
andm
are arrays' lengths. time is used to convertnums1
into set, time is used to convertnums2
, andcontains/in
operations are in the average case. 
Space complexity : in the worst case when all elements in the arrays are different.
Approach 2: Builtin Set Intersection
Intuition
There are builtin intersection facilities, which provide time complexity in the average case and time complexity in the worst case.
In Python it's intersection operator, in Java  retainAll() function.
Implementation
Complexity Analysis

Time complexity : in the average case and in the worst case when load factor is high enough.

Space complexity : in the worst case when all elements in the arrays are different.