Find m elements in n arrays by picking at most 1 element out of each of the n arrays

Question

I have n arrays, each of them contain an arbitrary amount of integers. No duplicates are possible within an array ([1,1,2] can't be one of the n arrays).

I also have an integer array of size m which is filled with integers from 1 to m (value_of_an_array_entry = array_index+1). Example: m = 4, the appropriate array is [1,2,3,4].

My question:

For given n and m, is it possible to find every element in the m array by picking at most 1 element out of each of the n arrays?

An Example:

n = 3, m = 3,

The n arrays: [1], [1, 2], [2, 3]

Output should be: Yes

(because we can find every element in the m array by picking at most 1 element out of each of the n arrays. Look at the n arrays and pick 1 from the first array, 2 from the second and 3 from the third array.)

This is an interview question, I received a hint to think about the Max flow problem (I don't see how this helps me).

Answer 1

You can build a graph like this: The graph is divided into the left part and the right part. The left part contains n vertices which represent the n arrays. The right part contains m vertices which represent the m numbers.

Then we consider these n arrays. If element k is contained in the i-th array, we draw an edge between the i-th vertex from the left and the k-th vertex from the right. Our goal is to choose m edges, so that each of the m vertices on the right is covered by the m edges exactly once, and the vertices on the left is covered at most once. This is a bipartite graph maximum matching problem, which can be solved by many algorithms, including max flow.