Peak element

Given an array arr[] where no two adjacent elements are same, find the index of a peak element. An element is considered to be a peak if it is greater than its adjacent elements (if they exist). If there are multiple peak elements, return index of any one of them. The output will be “true” if the index returned by your function is correct; otherwise, it will be “false”.

Note: Consider the element before the first element and the element after the last element to be negative infinity.

Examples :

Input: arr = [1, 2, 4, 5, 7, 8, 3]
Output: true
Explanation: arr[5] = 8 is a peak element because arr[4] < arr[5] > arr[6].

Input: arr = [10, 20, 15, 2, 23, 90, 80]
Output: true
Explanation: arr[1] = 20 and arr[5] = 90 are peak elements because arr[0] < arr[1] > arr[2] and arr[4] < arr[5] > arr[6]. 

Input: arr = [1, 2, 3]
Output: true
Explanation: arr[2] is a peak element because arr[1] < arr[2] and arr[2] is the last element, so it has negative infinity to its right.

Constraints:
1 ≤ arr.size() ≤ 10⁶
-2³¹ ≤ arr[i] ≤ 2³¹ – 1

Approach 01:

class Solution {
 public:
  int peakElement(vector<int>& arr) {
    int n = arr.size();
    if (n == 1) {
      return 0;
    } else if (n == 2) {
      if (arr[0] < arr[1]) {
        return 1;
      } else if (arr[0] > arr[1]) {
        return 0;
      } else {
        return -1;
      }
    }

    if (n > 2) {
      if (arr[0] > arr[1]) {
        return 0;
      } else if (arr[n - 1] > arr[n - 2]) {
        return n - 1;
      }
    }

    for (int i = 1; i < n - 1; ++i) {
      if (arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) {
        return i;
      }
    }

    return -1;
  }
};

class Solution:   
    def peakElement(self, arr):
        n = len(arr)
        if n == 1:
            return 0
        elif n == 2:
            if arr[0] < arr[1]:
                return 1
            elif arr[0] > arr[1]:
                return 0
            else:
                return False
        
        if n > 2:
            if arr[0] > arr[1]:
                return 0
            elif arr[-1] > arr[-2]:
                return n - 1
        
        for i in range(1, n - 1):
            if arr[i - 1] < arr[i] > arr[i + 1]:
                return i
        
        return False

Time Complexity

• Initial Check for Size 1 or 2:
  • If the array has only one or two elements, the function checks them in constant time, i.e., \(O(1)\).
• Edge Case for First or Last Element:
  • If the array has more than two elements, the first and last elements are checked for being peaks, which takes \(O(1)\).
• Linear Search for Peak:
  • If no peak is found at the boundaries, the function performs a linear scan through the array (from index 1 to \(n – 2\)) to find a peak.
  • This step takes \(O(n)\) time in the worst case.
• Overall Time Complexity:

  The time complexity is \(O(n)\), dominated by the linear scan of the array.

Space Complexity

• Input Array:
  • The input array arr is provided as an argument, and no additional space is allocated for it.
• Other Variables:
  • Variables like n and loop variables use \(O(1)\) space.
• Overall Space Complexity:

  The space complexity is \(O(1)\), as no extra data structures are used.