Daily LeetCode Problems: Problem 852. Peak Index in a Mountain Array

Conquering the Peak: Solving the Peak Index in a Mountain Array Problem

Introduction:

Welcome back to our daily problem-solving series! Today, we will embark on an exciting journey to conquer the peaks with LeetCode problem 852, titled “Peak Index in a Mountain Array.” This problem challenges us to find the peak index in a mountain array efficiently. We will thoroughly analyze the problem statement, devise an optimal approach, provide step-by-step pseudocode, explain the underlying concepts, and discuss the complexity analysis.

Problem Statement:

The problem presents us with a mountain array, which satisfies the following conditions:

1. The array length is at least 3 (arr.length >= 3).
2. There exists an index i (0 < i < arr.length — 1) such that:

• The elements before index i are in ascending order (arr[0] < arr[1] < … < arr[i — 1]).
• The element at index i is the peak of the mountain (arr[i] > arr[i + 1]).
• The elements after index i are in descending order (arr[i] > arr[i + 1] > … > arr[arr.length — 1]).

Our goal is to return the index i representing the peak of the mountain array.

Approach:

To efficiently find the peak index, we will utilize a binary search algorithm. We’ll start by initializing two pointers, left and right, to the first and last indices of the array, respectively. Then, we’ll perform binary search iterations to narrow down the search space until we find the peak index.

Pseudocode:

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 1

        while left < right:
            mid = left + (right - left) // 2

            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            else:
                right = mid

        return left

Complexity Analysis:

Let’s analyze the complexity of our solution:

• Time complexity: The binary search algorithm takes O(log(n)) time, where n is the length of the array. Therefore, the overall time complexity is O(log(n)).
• Space complexity: We only use a constant amount of extra space for the two pointers. Hence, the space complexity is O(1).

Step-by-Step Solution:

1. Initialize two pointers, left and right, to the first and last indices of the array, respectively.
2. Perform binary search iterations until left is less than right.
3. In each iteration, calculate the mid index as the average of left and right.
4. If arr[mid] is less than arr[mid + 1], update left to mid + 1, as the peak index must be on the right side of mid.
5. Otherwise, update right to mid, as the peak index must be on the left side of mid.
6. After the binary search, left will be pointing to the peak index. Return the value of left as the result.

Full Solution

Python

class Solution:
  def peakIndexInMountainArray(self, arr: List[int]) -> int:
    l = 0
    r = len(arr) - 1

    while l < r:
      m = (l + r) // 2
      if arr[m] >= arr[m + 1]:
        r = m
      else:
        l = m + 1

    return l

Java

class Solution {
  public int peakIndexInMountainArray(int[] arr) {
    int l = 0;
    int r = arr.length - 1;

    while (l < r) {
      final int m = (l + r) / 2;
      if (arr[m] >= arr[m + 1])
        r = m;
      else
        l = m + 1;
    }

    return l;
  }
}

C++

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int l=0;
        int r= arr.size()-1;

        while(l<r){
            int m= l+ (r-l)/2;
            if(arr[m]>arr[m+1]){
                r=m;
            }
            else{
                l=m+1;
            }
        }
        return l;
    
    }
};

Conclusion:

In this article, we conquered the peaks with LeetCode problem 852, “Peak Index in a Mountain Array.” By employing the power of binary search, we efficiently found the peak index in the mountain array. Understanding the problem’s conditions and utilizing the right algorithm helped us solve the problem in O(log(n)) time complexity. Keep practicing and stay tuned for more exciting LeetCode challenges in our daily series. Happy coding!