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 provides in/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 and m are arrays' lengths. time is used to convert nums1 into set, time is used to convert nums2, and contains/in operations are in the average case.

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


Approach 2: Built-in Set Intersection

Intuition

There are built-in 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

Analysis written by @liaison and @andvary