A peak of a matrix is defined as a location (i j), such that all of its neighboring element i.e. (i-1 j), (i+1 j), (i j-1)
(i j+1) not strictly greater than (i j). Here is an algorithm to find the peak of the algorithm in O(n) time:
- For a given matrix M, find its middle row/middle column(as given in the input) and find max element in that row/column.
- If that index is peak report it.
- Else, consider a sub-matrix that contains the element that violated peak condition and recursively call this procedure of that
with an input of choose column or row with the other was chosen.
This algorithm is supposed to be correct. But when I apply on this matrix
((2.1 2 2 13) (4 5 6 11) (7 8 8 8))
It given 2.1 as result which is not peak. Can anybody tell what am I missing? Here is the code
def algorithm4(problem, bestSeen = None, rowSplit = True, trace = None): # if it's empty, we're done if problem.numRow <= 0 or problem.numCol <= 0: return None subproblems =  divider =  if rowSplit: # the recursive subproblem will involve half the number of rows mid = problem.numRow // 2 # information about the two subproblems (subStartR1, subNumR1) = (0, mid) (subStartR2, subNumR2) = (mid + 1, problem.numRow - (mid + 1)) (subStartC, subNumC) = (0, problem.numCol) subproblems.append((subStartR1, subStartC, subNumR1, subNumC)) subproblems.append((subStartR2, subStartC, subNumR2, subNumC)) # get a list of all locations in the dividing column divider = crossProduct([mid], list(range(problem.numCol))) else: # the recursive subproblem will involve half the number of columns mid = problem.numCol // 2 # information about the two subproblems (subStartR, subNumR) = (0, problem.numRow) (subStartC1, subNumC1) = (0, mid) (subStartC2, subNumC2) = (mid + 1, problem.numCol - (mid + 1)) subproblems.append((subStartR, subStartC1, subNumR, subNumC1)) subproblems.append((subStartR, subStartC2, subNumR, subNumC2)) # get a list of all locations in the dividing column divider = crossProduct(list(range(problem.numRow)), [mid]) # find the maximum in the dividing row or column bestLoc = problem.getMaximum(divider, trace) neighbor = problem.getBetterNeighbor(bestLoc, trace) # update the best we've seen so far based on this new maximum if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen): bestSeen = neighbor if not trace is None: trace.setBestSeen(bestSeen) # return when we know we've found a peak if neighbor == bestLoc and problem.get(bestLoc) >= problem.get(bestSeen): if not trace is None: trace.foundPeak(bestLoc) return bestLoc # figure out which subproblem contains the largest number we've seen so # far, and recurse, alternating between splitting on rows and splitting # on columns sub = problem.getSubproblemContaining(subproblems, bestSeen) newBest = sub.getLocationInSelf(problem, bestSeen) if not trace is None: trace.setProblemDimensions(sub) result = algorithm4(sub, newBest, not rowSplit, trace) return problem.getLocationInSelf(sub, result)
I asked this question on codeforce blog but got no reply. Thats why i am asking here.