1
\$\begingroup\$

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

class Solution:
# @param num, a list of integer
# @return an integer
def findPeakElement(self, num):
    if len(num)==0: return None
    if len(num)==1: return 0
    return self.findPeakHelper(num,0,len(num)-1)
def findPeakHelper(self,num,start,end):
    mid = (start+end)/2
    if mid>start and mid < end:
        if(num[mid-1]<num[mid] and num[mid]>num[mid+1]):
            return mid
        if(num[mid-1]>num[mid]):
            return self.findPeakHelper(num,start,mid)
        else:
            return self.findPeakHelper(num,mid,end)
    else:
        if num[mid]>num[mid+1]:
            return mid
        else:return mid+1
\$\endgroup\$
3
  • \$\begingroup\$ Binary search works only on a sorted list. Post a working code otherwise this is off-topic. \$\endgroup\$ Feb 8, 2015 at 3:54
  • \$\begingroup\$ Does this code work? \$\endgroup\$ Feb 8, 2015 at 11:58
  • \$\begingroup\$ Yes this code works. \$\endgroup\$
    – mittu
    Feb 8, 2015 at 19:54

1 Answer 1

1
\$\begingroup\$

Your code looks functional. I quite like the idea of splitting the data in halves each time too. There are some things I would do differently, though.

First-up, the 1-liner if statement:

if len(num)==0: return None
if len(num)==1: return 0

also

   else:return mid+1

No, no no ... ;-0 That should be:

if len(num) == 0:
    return None
if len(num) == 1:
    return 0

and

    else:
        return mid + 1

Note that your pasted code is not indented correctly. You indented the class definition, but the class contents are at the same indentation level.

Additionally, I prefer whitespace between method definitions, an empty line.

Actually, I ran your code through a pep8 checker, it pointed out all the compressed-statements too (no whitespace around operators). Here's your code in a format that passes the pep8 check:

class Solution:

    # @param num, a list of integer
    # @return an integer
    def findPeakElement(self, num):
        if len(num) == 0:
            return None
        if len(num) == 1:
            return 0
        return self.findPeakHelper(num, 0, len(num) - 1)

    def findPeakHelper(self, num, start, end):
        mid = (start + end) / 2
        if mid > start and mid < end:
            if(num[mid - 1] < num[mid] and num[mid] > num[mid + 1]):
                return mid
            if(num[mid - 1] > num[mid]):
                return self.findPeakHelper(num, start, mid)
            else:
                return self.findPeakHelper(num, mid, end)
        else:
            if num[mid] > num[mid + 1]:
                return mid
            else:
                return mid + 1

Note:

  • spaces surrounding operators
  • statements on new line, not the same line as the if/else conditions

Now, about your algorithm...

Really, there's nothing wrong with it, but I believe you can simplify the logic a bit if you treat the mid-point only when needed. Consider the following helper function:

class Solution:

    # @param num, a list of integer
    # @return an integer
    def findPeakElement(self, num):
        if len(num) == 0:
            return None
        if len(num) == 1:
            return 0
        return self.findPeakHelper(num, 0, len(num) - 1)

    def findPeakHelper(self, num, start, end):
        span = end - start
        # span of 1 indicates 2 elements
        if span == 1:
            return start if num[start] > num[end] else end
        mid = start + span / 2
        if num[mid] < num[mid + 1]:
            return self.findPeakHelper(num, mid, end)
        return self.findPeakHelper(num, start, mid)

Note how you don't need the else-statements if the if-statement has a guaranteed return.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks @rolfl for your pointers. The code I pasted was already been submitted in leetcode and was accepted but I felt I could improve the code a lot for which you immensely helped. Being the one liner pointers to how I could improve and on if-else statements. Thanks a lot.:) Your code looks very neat. \$\endgroup\$
    – mittu
    Feb 8, 2015 at 20:10

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.