162.Find Peak Element

Tags: [divide_conquer], [binary_search], [trick], [range]

Com: {g}

Hard: [##]

Link: https://leetcode.com/problems/find-peak-element/#/description

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

Given an input array wherenum[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 thatnum[-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.

click to show spoilers.

Note:

Your solution should be in logarithmic complexity.

Better Solution: Divide And Conquer, Binary Search

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return None

        size = len(nums)
        start = 0
        end = size - 1
        while start < end:
            mid = start + (end - start) / 2

            # the mid is always a 'smaller' mid. think about start = 0, end = 1, the mid = 0.
            # becaue the while loop condidtion is start < end, 
            # which means there are at least two elements, and mid is the 'smaller' mid,
            # so the mid + 1 must be in the range.

            if nums[mid] < nums[mid + 1]:
                # because the nums[-1] and nums[n] are both minus inifinte,
                # so if the nums[right] > nums[mid], there must exist one of peaks.
                start = mid + 1
            else:
                # nums[mid] >= nums[mid + 1], the mid can be the peak, 
                # so end = mid.
                end = mid

        # at this point, start == end.
        return start

Revelation:

• mid = start + (end - start) / 2, will give us a 'smaller' mid.
• while start < end, which guarantees that if we are inside of the while loop, there are at least two elements.

Solution: Divide And Conquer, Binary Search

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return None

        size = len(nums)
        start = 0
        end = size - 1
        while start < end:
            mid = start + (end - start) / 2

            if (mid - 1 < 0 and mid + 1 >= size) or\
               (mid - 1 < 0 and nums[mid] > nums[mid + 1]) or\
               (mid + 1 >= size and nums[mid] > nums[mid - 1]) or\
               (0 <= mid - 1 < mid + 1 < size and nums[mid - 1] < nums[mid] and nums[mid + 1] < nums[mid]):
                return mid
            elif 0 <= mid - 1 < mid + 1 < size:
                if nums[mid - 1] >= nums[mid + 1]:
                    end = mid - 1
                else:
                    start = mid + 1
            elif mid - 1 >= 0:
                # left in the range, means right out of range.
                end = mid - 1
            else:
                # right in the range, means left out of range.
                start = mid + 1

        return start

Revelation:

• Discuss the case by case carefully to cover all cases.

Note:

• Time complexity = O(lgn), n is the number of elements of the given array.