0

I happened to read a variation of the peak finding algorithm, where I have to print all the local peaks in the input 2D matrix. That is an element at i,j can be a peak if it is greater than or equal to all its neighboring elements,ie elements at i-1,j ; i+1,j ; i,j-1 ; i,j+1. This problem can be done in O(n^2) complexity. But can we do it in O(nlogn) complexity. I have tried several method but nothing is working out to solve it in O(nlogn) complexity.

Ravi
  • 79
  • 1
  • 2
  • 5
  • This question is a duplicate of [this](http://stackoverflow.com/questions/9781328/finding-local-maxima-in-a-2d-array). However, no formal correct answer was actually given there, hence I upvoted. – Tim Biegeleisen Oct 02 '16 at 06:18
  • Click [here](http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf) for some course notes taken from an MIT lecture which described an `O(nlgn)` algorithm for thia problem. – Tim Biegeleisen Oct 02 '16 at 06:20
  • 2
    There can be n^2/2 peaks in the matrix. So you cannot get better than O(n^2). – Nico Schertler Oct 02 '16 at 13:10
  • @TimBiegeleisen Yea..I went though that MIT materials but it just finds the maxima of the matrix. It doesnt find all the local maximum. – Ravi Oct 03 '16 at 03:35
  • Possible duplicate of [Find peak (regions) in 2D data](https://stackoverflow.com/questions/43852754/find-peak-regions-in-2d-data) – Cris Luengo May 01 '18 at 17:48

0 Answers0