Leetcode 162. Find Peak Element

Problem Explanation

In this problem, we are given an array of distinct numbers and we need to find the index of a 'peak' element. A peak element is defined as an element that is larger than both its neighbors.

For instance, in the array [1,2,3,1], number 3 is a peak element because it is larger than both 2 and 1, its neighbors. The index of 3 is 2, so the function should return 2.

It's important to note that the array can contain multiple peaks. In this case, returning the index of any one of the peaks is fine. For example, in the array [1,2,1,3,5,6,4], both 2 and 6 are peak elements. So, the function could return either 1 (the index of 2) or 5 (the index of 6).

Finally, the problem requires that the solution should be in logarithmic complexity. This suggests that a binary search type of approach could be ideal for this problem.

Solution Approach

The goal is to use binary search to find a peak element. The main idea is as follows: we initially consider the entire array as our search space. We compute the midpoint of this space and compare the value at the midpoint with the value at the subsequent index. If the value at the midpoint is greater or equal, it means that a peak element could potentially be towards the left side of the midpoint (including the midpoint). Otherwise, a peak element can only exist towards the right of the midpoint. We continue this process, reducing our search space by half at every step, until our search space is down to a single element.

Let's take the array [1,2,1,3,5,6,4] as our example:

1Initialization: l = 0, r = 6, search space is [1,2,1,3,5,6,4]
2Iteration 1: m = 3, nums[3] = 3 < nums[4] = 5 -> l = 4, search space is [3,5,6,4]
3Iteration 2: m = 5, nums[5] = 6 > nums[6] = 4 -> r = 5, search space is [3,5,6]
4... etc, until the search space down to a single element

Solution

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int findPeakElement(vector<int>& nums) {
6    int l = 0;
7    int r = nums.size() - 1;
8
9    while (l < r) {
10      const int m = (l + r) / 2;
11      if (nums[m] >= nums[m + 1])
12        r = m;
13      else
14        l = m + 1;
15    }
16
17    return l;
18  }
19};

Python Solution

1
2python
3class Solution:
4  def findPeakElement(self, nums):
5    l, r = 0, len(nums) - 1
6    while l < r:
7      m = (l + r) // 2
8      if nums[m] >= nums[m + 1]:
9        r = m
10      else:
11        l = m + 1
12    return l

Java Solution

1
2java
3class Solution {
4  public int findPeakElement(int[] nums) {
5    int l = 0, r = nums.length - 1;
6    while (l < r) {
7      int m = (l + r) / 2;
8      if (nums[m] >= nums[m + 1])
9        r = m;
10      else
11        l = m + 1;
12    }
13    return l;
14  }
15}

JavaScript Solution

1
2javascript
3var findPeakElement = function(nums) {
4  let l = 0, r = nums.length - 1;
5  while (l < r) {
6    let m = Math.floor((l + r) / 2);
7    if (nums[m] >= nums[m + 1])
8      r = m;
9    else
10      l = m + 1;
11  }
12  return l;
13};

C# Solution

1
2csharp
3public class Solution {
4  public int FindPeakElement(int[] nums) {
5    int l = 0, r = nums.Length - 1;
6    while (l < r) {
7      int m = (l + r) / 2;
8      if (nums[m] >= nums[m + 1])
9        r = m;
10      else
11        l = m + 1;
12    }
13    return l;
14  }
15}

Analysis of the Approaches

As mentioned, it's critical that our solution operates in logarithmic time complexity to handle larger inputs efficiently. Indeed, all of the above solutions - C#, C++, Python, JavaScript, and Java - meet this requirement due to the binary search method that they employ. The binary search method splits the problem size in half with each iteration. Hence, these solutions have a time complexity of O(log(N)) where N is the size of the input array.

Each of our solutions uses a similar logic flow:

1. Define a search space by initializing two pointers, l and r.
2. Perform a binary search until the search space is reduced to a single element:
   1. Calculate the midpoint, m, of the current search space.
   2. Compare the value at m with the value at m + 1.
   3. If nums[m] is less than nums[m + 1], a peak element can only exist towards the right of m; so, we set l to m + 1 to redefine the search space to the right section of the array.
   4. Conversely, if nums[m] is greater than or equal to nums[m + 1], a peak element could exist towards the left (including m). So, we redefine the search space to the left section of the array by setting r = m.
3. Ultimately, the index l (which is equal to r at the end of our search) is the index of a peak element in the array.

The space complexity for all these solutions is O(1), which is the ideal case for space complexity.

Conclusion

Using a binary search-based approach, we can efficiently find a peak element in a distinct numbers array in O(log(N)) time complexity and O(1) space complexity. The binary search operation allows us to iteratively halve the search space, making it an optimal solution for large array inputs. This methodology is similarly implemented in C++, Python, Java, JavaScript, and C# solutions, demonstrating its versatility across various programming languages.