I got this question in the programming round of a job Interview. Any pointers towards an efficient solution would be much appreciated.
Given an n by m matrix and an integer k, where each element in the matrix is an integer from 1 to k, remove all elements from the matrix. To remove an element, select an element and remove it and all occurrences of the element in the same row and column of the matrix. Return the minimum number of such operations required to remove all elements from the matrix.
Example: Given a matrix as follows:
{ 2, 2, 1 },
{ 1, 1, 1 },
{ 2, 3, 3 },
we can choose the element at (2,3) in the first operation and remove it. Then the matrix looks like:
{ 2, 2, x },
{ x, x, x },
{ 2, 3, 3 },
we can choose the element at (1,1) in the sexond operation and remove it. Then the matrix looks like:
{ x, x, x },
{ x, x, x },
{ x, 3, 3 },
we can choose the element at (3,3) in the third operation and remove it. Then the matrix looks like:
{ x, x, x },
{ x, x, x },
{ x, x, x },
Output:
3
Constraints:
- 1 <= n <= 100
- 1 <= m <= 100
- 1 <= k <= 50