Find indices of equal cells in a matrix

Question

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)?

Answer 1

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