1
$\begingroup$

I am trying to find the indices of all the equal elements in a matrix $\left ( n\times m \right )$. For each pair of matching cell, I will perform a specific function on them. For example:

$ \begin{bmatrix} 2 & 1 & 3\\ 4 & 1 & 5\\ 2 & 3 & 2 \end{bmatrix}$

The cell (1, 1) whose value is 2 matches with cells (3, 1) and (3, 3). I tried to do this by looping through the whole matrix twice which is far away from being efficient $O(n^2m^2)$. Is there a more efficient way to do this search (at least to avoid duplicates)?

$\endgroup$

1 Answer 1

1
$\begingroup$

You can use sorting ($O(nm \log nm)$) or a hash table (randomized $O(nm)$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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