Optimal Approach

Algorithm

Initialize two pointers, one at the top (start) and one at the bottom (end) of the matrix
Compare the individuals at the top and bottom pointers
If the person at the top pointer knows the person at the bottom pointer, move the top pointer down (the top person cannot be the celebrity)
If the person at the bottom pointer knows the person at the top pointer, move the bottom pointer up (the bottom person cannot be the celebrity)
If neither knows the other, increment both pointers (neither can be the celebrity)
After the traversal, the remaining candidate at the top pointer is the potential celebrity
Check if the candidate is a valid celebrity by ensuring that everyone knows this person and this person knows no one
If the candidate is valid, return the index; otherwise, return -1 indicating no celebrity