@shady: There were no specific constraints. Actually, they didn't expect any best solution. People who wrote brute force also got shortlisted. Brute force would be Just picking a number one by one from first row and then checking other rows for existence of this number. I think it is a O(n^3) algorithm where n--> number of rows/cols
Another approach might be, we can sort each row in O(nlogn). So total is O(n^2 * log(n)). Take number one by one from first row and then binary search on remaining rows. It is O(logn) in one row. So total binary search cost for searching one element in n rows is O(nlogn). In worst case where last element of first row occurs in each row, complexity of this algorithm seems to be O(n^2 * logn ) Correct me if I'm wrong. Anyone having better solution to this, please comment.. Also as second algorithm is quite complex to implement and in question they explicitly mentioned matrix is 3X3, So brute force would be the fastest i guess... :) :) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
