A simple way of doing this is to use hashsets (assumes no intersection operation is available). Simply create 2 hashsets, one for each array, this takes O(n) time. Now simply iterate over both hashsets (or arrays it doesn't really matter) and lookup in the opposite hashset for the same value (O(n) time). Overall, O(n) time and space complexity. If space is an issue, an n*log n solution could involve efficiently merging and sorting the arrays and then passing over it looking for duplicate values. If they exist then you have an intersection. O(n*log n) time complexity (because of the sort) and no extra space required (unless required for the merge and sort).