3

I'm completely new to Python, thus the question. I'm trying to solve a standard interview question, which is finding a peak in an array. A peak is defined as a number which is greater than it's left and right neighbor. I'm trying to find the largest such peak.

This is my code:

def main():
    arr = [7, 12, 13, 8, 2, 16, 24, 11, 5, 1]
    print(find_peak(arr))


def find_peak(arr):
    return _find_peak(arr, 0, len(arr))


def _find_peak(arr, start, stop):

    mid = (start + stop) // 2

    if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:
        return arr[mid]

    elif arr[mid] < arr[mid - 1]:
        _find_peak(arr, 0, mid - 1)

    elif arr[mid] < arr[mid + 1]:
        _find_peak(arr, mid + 1, stop)


if __name__ == '__main__':
    main()

The output of this program is None, where as the expected output is 24. Any help appreciated.

Improve this question
8
  • 1
    You don't return any values from _find_peak, so the result will always be None. Commented Jan 29, 2016 at 22:32
  • 1
    Largest peak? Not possible. Even if you just want to find any peak, you can't do it in O(log n) with this definition of "peak"; it's only possible for a definition where a peak is any element at least as great as its neighbors, rather than greater. Commented Jan 29, 2016 at 22:33
  • Apologies, amended that wrong line. It slipped through the crack. Commented Jan 29, 2016 at 22:33
  • You should return _find_peak... in the elif parts.. But you'll still get bad result (at least not None) :) Commented Jan 29, 2016 at 22:33
  • I wonder whether you're looking for this: gist.github.com/alvations/29a970409f7bebf1ad9b Commented Jan 29, 2016 at 23:10

5 Answers 5

Reset to default
4

Data

arr = [7, 12, 13, 8, 2, 16, 24, 11, 5, 1]

A one-liner:

One line should be enough:

max_peak = max(x2 for x1, x2, x3 in zip(arr, arr[1:], arr[2:]) if x1 < x2 > x3)

In a loop

Maybe easier to understand when you are new to Python:

peak = float('-inf')
for x1, x2, x3 in zip(arr, arr[1:], arr[2:]):
    if x1 < x2 > x3:
        peak = max(peak, x2)
print(peak)

Output:

24

All peaks

You can also use a one-liner to get all peaks:

>>> [x2 for x1, x2, x3 in zip(arr, arr[1:], arr[2:]) if x1 < x2 > x3]
[13, 24]

and get the greatest one with max() on the result.

Explanation

Let's have a look at some of the components of the solution. I am working with Python 3 here, as everybody should. ;)

You can slice lists.

>>> arr = [7, 12, 13, 8, 2, 16, 24, 11, 5, 1]

This gives you all of the list but the first element:

>>> arr[1:]
[12, 13, 8, 2, 16, 24, 11, 5, 1]

Here its starts with element three:

>>> arr[2:]
[13, 8, 2, 16, 24, 11, 5, 1]

The zip() function zips multiple sequences together. To visualize what happens, you can convert the zip object into a list:

>>> list(zip(arr, arr[1:], arr[2:]))
[(7, 12, 13),
 (12, 13, 8),
 (13, 8, 2),
 (8, 2, 16),
 (2, 16, 24),
 (16, 24, 11),
 (24, 11, 5),
 (11, 5, 1)]

Python supports tuple unpacking. This allows to assign individual names to all members of a tuple:

>>> x1, x2, x3 = (7, 12, 13)
>>> x1
7
>>> x2
12
>>> x3
13

Another nice feature is the comparison of more than two objects:

>>> 10 < 12 > 8
True

This is equivalent to:

>>> (10 < 12) and (12 > 8)
True

Python offers list comprehensions:

>>> [x * 2 for x in range(2, 6)]
[4, 6, 8, 10]

Generator expression work in a similar way but don't produce a list but an iterator and can be consumed without using lots of memory:

>>> sum(x * 2 for x in range(2, 6))
28
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Can you explain the code a bit. This is going way above me.
Added a bit of explanation. Covering all this in detail with examples and exercises can be easily one day of teaching. ;)
0

you are missing a return statement for your two elif cases

Improve this answer

3 Comments

This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review
@Prune, this answers the question. It may not be a high quality answer, but it does provide an answer. Please be more careful when reviewing. Ensure that it actually is not an answer before making it as such.
From the SO guidelines I've seen, you should provide correct return statements to fully qualify as a valid answer. That's my interpretation (including answers I have left a little short), hardly canonized SO practice.
0

I think the 13 also is a peak (greater than 12 and 8).

Try this approach:

def main():
    arr = [7, 12, 13, 8, 2, 16, 24, 11, 5, 1]
    print(find_peaks(arr))


def find_peaks(arr):
    return list(_search(arr))


def _search(arr):
    last = len(arr) - 1
    for i, e in enumerate(arr):
        if not any((i > 0 and arr[i-1] > e, i < last and arr[i+1] > e)):
            yield e


if __name__ == '__main__':
    main()

If you don’t understand anything, ask!

Improve this answer

Comments

0

Another approach – using only one function:

def main():
    arr = [7, 12, 13, 8, 2, 16, 24, 11, 5, 1]
    print(find_peaks(arr))


def find_peaks(arr):
    last = len(arr) - 1
    return [
        e for i, e in enumerate(arr)
        if not any((i > 0 and arr[i-1] > e, i < last and arr[i+1] > e))
    ]


if __name__ == '__main__':
    main()
Improve this answer

3 Comments

It would really help if you could explain your approach. I'm a stark newbie in python.
The [... for ...] syntax is a list comprehension: it builds a list of elements for each iteration over the iterable after in. The enumerate() function returns a iterable of which each element is a tuple containing the index of an element (i) of the arr and the element itself (e). The if inside the list comprehesion filters the elements: any() returns True if any element of the parameter is true, so it checks if the current element is greater than the left (arr[i-1]) and right (arr[i+i]) neighbours (nor left or right one is greater).
In other words: I just filter the original arr, selecting only the elements that’s not less than left neighbour, nor less than right one (if not any(…)).
-1

I don't think you can find a peak in O(log N) time, because by definition the items cannot be in order, and there is no way to predict the peaky-ness of any item in a list given other items, except that comparing item N with item N+1 is presumably reflexive - it tells you that either N or N+1 might be a peak. That gets you to N/2 compares, which must then be followed by N/2 more compares to check the other side of the peak.

Here's a local_maxima(iterable) function that you can use with max() to find peaks. It treats start/end elements as peaks if they are greater than their one neighbor.

data = [7, 12, 13, 8, 2, 16, 24, 11, 5, 1, None, 2, None, 3, 4, None, 5, 1, None]
firstpeak = [12, 7, 9, 8]
lastpeak = [1, 2, 3, 4]

def local_maxima(it):
    """Find local maxima in iterable _it_. Compares with None using
    `is (not) None`, and using operator `<`."""

    peaking = False
    last = None

    for item in it:

        # Deal with last item peaking
        if peaking and (item is None or item < last):
            yield last
            peaking = False
        elif item is None:
            peaking = False
        elif last is None or last < item:
            peaking = True
        else:
            peaking = False

        last = item

    if peaking:
        yield last

print([x for x in local_maxima(data)])
print("Highest:", max(local_maxima(data)))
print([x for x in local_maxima(firstpeak)])
print("Highest:", max(local_maxima(firstpeak)))
print([x for x in local_maxima(lastpeak)])
print("Highest:", max(local_maxima(lastpeak)))
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.