1
\$\begingroup\$

I attempted a solution to a seemingly simple problem:

Peak Finder

Let input be a list. input[i] is a peak if input[i] > input[i + 1] and input[i] > input[i - 1].

Implement a recursive algorithm of time complexity \$O(\log n)\$ to find a peak if it exists.

def peakFinder(input):
        n = len(input)
        middleIndex = n/2
        middleIsMax = input[middleIndex] > input[middleIndex + 1] and input[middleIndex] > input[middleIndex - 1]

        # base case 
        if middleIsMax:
            return input[middleIndex]

        leftArray = input[:middleIndex]
        rightArray = input[middleIndex:]

        moveRight = input[middleIndex + 1] > input[middleIndex] and input[middleIndex + 1] > input[middleIndex - 1]

        moveLeft = input[middleIndex - 1] > input[middleIndex] and input[middleIndex - 1] > input[middleIndex + 1]

        # recursive case
        if moveRight:
            return peakFinder(rightArray)
        elif moveLeft:
            return peakFinder(leftArray)    

    print peakFinder([2, 41, 17, 11, 13, 7])

Are there improvements to be made? Is the time complexity \$O(\log n)\$?

\$\endgroup\$
  • 5
    \$\begingroup\$ I think O(n) time will be needed if there can be arbitrarily large flat sections in input. \$\endgroup\$ – Janne Karila Jan 2 '15 at 8:21
  • 3
    \$\begingroup\$ Consider the list x = [1] + [0] * n; random.shuffle(x). Finding the index of the 1 is equivalent to finding the peak and takes \$\mathcal{O}(n)\$ time. If there can't be any flats, consider x = list(range(n)); x[random.randrange(n)] += 2. Again, this is \$\mathcal{O}(n)\$ since it is isomorphic to the previous question. \$\endgroup\$ – Veedrac Jan 2 '15 at 8:44
  • 4
    \$\begingroup\$ If I change to print peakFinder([2, 9, 17, 11, 13, 7]) I get a runtime error. I think that you are missing a base case and skipping possible solutions. \$\endgroup\$ – Brythan Jan 2 '15 at 8:58
  • \$\begingroup\$ I will look into fixing my implementation. Thank you for weighing in. \$\endgroup\$ – ng-hacker-319 Jan 2 '15 at 9:07
  • 2
    \$\begingroup\$ This showed up in the close queue as being broken. I feel OP should be given benefit of the doubt as it appears they didn't know it was broken. I think we can consider the case @Brythan found to be a bug/corner case. \$\endgroup\$ – RubberDuck Jan 2 '15 at 15:22
3
\$\begingroup\$
  • Slicing a list, as in leftArray = input[:middleIndex], creates a copy and takes \$O(n)\$ time. You can avoid that by passing the whole list together with left and right indices as function arguments.
  • Another problem with the slicing approach is that you need to look at three values to recognize the peak, but the slices can become shorter than three elements.
  • Python's chained comparison would be handy here:

    middleIsMax = input[middleIndex - 1] < input[middleIndex] > input[middleIndex + 1]
    
\$\endgroup\$
1
\$\begingroup\$
  • the definition of this problem should include the equal case, otherwise you will have to do a linear search on this problem.

input[i] is a peak if input[i] >= input[i + 1] and input[i] >= input[i - 1].

  • this method does not work for input [0, 0, 0], because there is no max, you can not moveRight or moveLeft according to your code.

  • this method cannot handle null, empty array, or one item array. (I do not know much about Python, so let me know if I am wrong on this one.)

  • No need to compare input[middleIndex + 1] with input[middleIndex - 1], because all you care about is if they are greater than input[middleIndex]

Edited: Here is my implementation of peak finder in Java. Hope it can help.

Implementation of peak finder

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.