Question

Formatted question description: https://leetcode.ca/all/162.html

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

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1
nums[i] != nums[i + 1] for all valid i.

Algorithm

To find the first local peak in an array, we need to search for a number that is larger than its two adjacent numbers. However, traversing the entire array to find the maximum value will result in a Time Limit Exceeded error. Instead, we can follow the below approach to find the first local peak:

To avoid out-of-bounds errors, we can add two integer minimums (-∞) at the beginning and end of the array, as the title specifies that nums[-1] = nums[n] = -∞.
We then traverse from the second number to the second last number, so that we don’t cross the boundary.
If the second number is smaller than the first number, it means that the first number is a local peak.
Otherwise, we continue to traverse backward in an increasing trend. If we find a number that is smaller than the previous number, it means that the previous number is a local peak and we return its index.
If the loop ends, it means that the original array is an increasing array, and we return the last index.

However, there is an important corner case to consider. When the original array contains only one number, and it is the minimum value of an integer, adding numbers at the beginning and end will create a horizontal line, and there will be no peak value. Therefore, we need to check if the array contains only one number at the beginning, and if so, we return its index directly.

Code

public class Find_Peak_Element {

    public class Solution_noArrayCopy {
        public int findPeakElement(int[] nums) {
            for (int i = 1; i < nums.length; ++i) {
                if (nums[i] < nums[i - 1]) return i - 1;
            }
            return nums.length - 1;
        }
    }

    class Solution {
        public int findPeakElement(int[] nums) {
            if (nums.length == 1) return 0;
            int[] newNums = new int[nums.length + 2];
            System.arraycopy(nums, 0, newNums, 1, nums.length);
            newNums[0] = Integer.MIN_VALUE;
            newNums[newNums.length - 1] = Integer.MIN_VALUE;
            for (int i = 1; i < newNums.length - 1; ++i) {
                if (newNums[i] > newNums[i - 1] && newNums[i] > newNums[i + 1]) return i - 1;
            }
            return -1;
        }
    }

    public class Solution_binary {
        public int findPeakElement(int[] nums) {
            int l = 0, r = nums.length - 1;

            // Compare the size with the immediately following element. If it is larger, the peak value is in the front, and if it is smaller, it is in the back. So you can find a peak
            while (l < r) {
                int mid = (l + r) / 2;
                if (nums[mid] > nums[mid + 1])
                    r = mid;
                else
                    l = mid + 1;
            }
            return l;
        }
    }
}

############

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

// OJ: https://leetcode.com/problems/find-peak-element/
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    int findPeakElement(vector<int>& A) {
        int L = 0, R = A.size() - 1;
        while (L <= R) {
            long M = (L + R) / 2, left = M == 0 ? LONG_MIN : A[M - 1], right = M == A.size() - 1 ? LONG_MIN : A[M + 1];
            if (A[M] > left && A[M] > right) return M;
            if (A[M] < left) R = M - 1;
            else L = M + 1;
        }
        return -1;
    }
};

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1
        return left

############

class Solution(object):
  def findPeakElement(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    start, end = 0, len(nums) - 1
    while start + 1 < end:
      mid = start + (end - start) / 2
      if nums[mid] < nums[mid + 1]:
        start = mid
      else:
        end = mid
    if nums[start] > nums[end]:
      return start
    return end

func findPeakElement(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := (left + right) >> 1
		if nums[mid] > nums[mid+1] {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

function findPeakElement(nums: number[]): number {
    let left = 0,
        right = nums.length - 1;
    while (left < right) {
        let mid: number = (left + right) >> 1;
        if (nums[mid] <= nums[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

162 - Find Peak Element

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions