DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Intersection of Two Arrays

easyArrays and hashing

Problem statement

You are given two lists of integers, nums1 and nums2. Return every value that appears in both lists. Each value should appear only once in the result, even if it repeats in the inputs. The result can be in any order.

For example: which ports are open on both hosts, given each host's list of open ports.

Examples

Example 1

Input: nums1 = [3, 1, 3, 7], nums2 = [7, 3, 8]

Output: [3, 7]

Explanation: 3 and 7 are in both lists. 3 repeats in nums1 but is reported once.

Example 2

Input: nums1 = [1, 2], nums2 = [4, 5]

Output: []

Explanation: The lists share no values.

Hints

Approach

Put nums1 in a set. Then walk nums2 and collect every value that is in that set into a second set, which removes repeats.

  1. Build first = set(nums1).
  2. For each value in nums2, if it is in first, add it to found.
  3. Return found as a list.

In Python the built-in set intersection set(nums1) & set(nums2) does exactly this in one line.

ComplexityTime O(n + m)Space O(n + m)
Python
class Solution:
def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
return list(set(nums1) & set(nums2))

Follow-up questions

  • Return values that are in nums1 but not in nums2.
  • nums2 is stored on disk and too big for memory, but it is sorted. How do you compute the intersection?

Frequently asked questions

The smaller one, when you can choose. The set's memory is proportional to the list you put in it, and the other list is only streamed through.

Count the values of one list in a map, then walk the other list and emit a value each time its count is still above zero, decrementing as you go.

Set intersection and difference are everyday operations: hosts in both the inventory and the monitoring system, packages installed on two servers, or security groups shared by two instances. comm and sort | uniq in the shell are the same idea.