2D Peak Finding Algorithm In O(n) Worst Case Time?
Answer : Let's assume that width of the array is bigger than height, otherwise we will split in another direction. Split the array into three parts: central column, left side and right side. Go through the central column and two neighbour columns and look for maximum. If it's in the central column - this is our peak If it's in the left side, run this algorithm on subarray left_side + central_column If it's in the right side, run this algorithm on subarray right_side + central_column Why this works: For cases where the maximum element is in the central column - obvious. If it's not, we can step from that maximum to increasing elements and will definitely not cross the central row, so a peak will definitely exist in the corresponding half. Why this is O(n): step #3 takes less than or equal to max_dimension iterations and max_dimension at least halves on every two algorithm steps. This gives n+n/2+n/4+... which is O(n) . Important detail: we split...