algoadvance

Leetcode 852. Peak Index in a Mountain Array

Problem Statement

Given a mountain array arr, return the index i such that the following conditions hold:

• arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
• arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

You must solve it in O(log(arr.length)) time complexity.

Example:

Input: arr = [0,2,1,0]
Output: 1

Constraints:

• The length of arr will be at least 3.
• arr will be a mountain array (i.e., there exists exactly one i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]).

Clarifying Questions

1. Is the array guaranteed to be a valid mountain array?
   • Yes, it is explicitly mentioned in the problem statement.
2. Can there be duplicate values in the array?
   • No, given the description, the array values are strictly increasing and then strictly decreasing.

Strategy

Given the constraints and the requirement for O(log n) time complexity, a binary search approach is ideal.

• Binary Search Approach:
  • Initialize two pointers: left at the start of the array and right at the end of the array.
  • Calculate the mid-point index.
  • Compare the middle element arr[mid] with the next element arr[mid+1]:
    • If arr[mid] < arr[mid + 1], it means we are in the ascending part of the mountain, and the peak must be to the right of mid. Move the left pointer to mid + 1.
    • If arr[mid] > arr[mid + 1], it means we are in the descending part of the mountain, and the peak can be at mid or to its left. Move the right pointer to mid.
  • Continue until left equals right. The left (or right) will be the peak index.

Code

#include <vector>

class Solution {
public:
    int peakIndexInMountainArray(std::vector<int>& arr) {
        int left = 0, right = arr.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] < arr[mid + 1]) {
                // We are in the ascending part of the mountain
                left = mid + 1;
            } else {
                // We are in the descending part of the mountain, or at the peak
                right = mid;
            }
        }
        
        // left and right converge to the peak index
        return left;
    }
};

Time Complexity

• The time complexity of this solution is O(log n) because we are performing a binary search on the array.
• The space complexity is O(1), as no additional space is used except for a few variables for indexing.

This solution ensures that we efficiently find the peak index in the mountain array using the constraints provided.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?