Directi Interview Question
Software Engineer / DevelopersSo funny... even for this type of problems people can't think out of graph!
O(n^2) time is sufficient to do this in straight forward manner. No solution CAN'T exist that has lower complexity to find ALL local maxima!
Think the matrix as a graph, we visit graph with BFS. For each node, it has state {non-visited, visit-drop, visit-target}. We add all neighbour into queue, then check & mark status until we finished the queue.
- Anonymous August 24, 2011