1
$\begingroup$

Given two integer arrays a and b and a map m which for each element e of the array a returns an array p of possible mappings, map every e of a to an element k of b so that m[e] contains k, no element of a or b is mapped twice and the number of non-mapped integers in a is minimal. Note that both a and b may have repetitive elements.

For example:

a = [1,2], b = [3,4], m = [1 => [3,4], 2 => [3]]

We see that 1 can be mapped both to 3 and to 4. However since we want the number of mapped elements to be maximal we must map 1 to 4 because 2 can only be mapped to 3. So the result here would be:

1 => 4, 2 => 3

So far I've only come up with the bruteforce solution which is to just try every possible mapping for every value in a. However this solution has a time complexity of O(n) = !n * k where n is the number of elements in a and k is the number of possible mappings.

How could you optimize this further to get the most efficient algorithm for solving the problem?

$\endgroup$
1
$\begingroup$

This problem can be transformed to a maximum flow problem.

    Transformation to a flow network
Consider each element in either array $A$ or $B$ as a distinct node.
If element $e$ in $A$ can be mapped to element $k$ in $B$, add an edge from $e$ to $k$.
Add source node $s$. Add an edge from $s$ to each element in $A$.
Add sink node $t$. Add an edge from each element in $B$ to $t$.
Let the capacity of every edge be 1.
We have obtained $G$, a flow network.

We can verify that the maximum number of mapped element in $A$ is exactly the maximal flow of $G$.


There are many polynomial-time algorithms to compute the maximum flow of a flow-network. Edmonds–Karp algorithm and Dinic's algorithm are taught in many introductory course in graph algorithms. Implementations in various programming languages can be found readily online.


Exercise 1. Verify the maximum number of mapped element in $A$ is the maximal flow of $G$.

Exercise 2. The flow network that we constructed above, using one node for each element, is a unit-capacity flow network. To increase efficiency, describe how we can construct a new flow network using one node for each group of repeated elements instead, so that the maximum number of mapped element in $A$ is the maximal flow of the new flow network still.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.