algoadvance

Leetcode 852. Peak Index in a Mountain Array

Problem Statement

Given an array of integers arr that is strictly increasing until it reaches a peak element and then strictly decreasing, find the index of the peak element. You can assume that arr is guaranteed to be a mountain array.

A mountain array is defined as an array that:

1. arr.length >= 3
2. There exists some 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. What is the range of the array size?
   • The array will have a size of at least 3 and could go up to a very large size.
2. What is the range of the element values in the array?
   • The elements in the array can be any integer values.
3. Is there always exactly one peak element in the array?
   • Yes, as per the definition, there will be one peak element in the array.

Strategy

To solve this problem efficiently, we can use binary search, given the properties of the mountain array (strictly increasing then strictly decreasing). Binary search enables us to find the peak element in O(log n) time, which is more efficient than a linear scan.

Approach:

1. Initialize two pointers: left at the start of the array and right at the end of the array.
2. While left is less than right:
   • Compute mid as the middle index between left and right.
   • If arr[mid] is less than arr[mid + 1], it means the peak lies to the right side, so we shift left to mid + 1.
   • Otherwise, the peak lies to the left side or is the current element, so we shift right to mid.
3. When left equals right, we have found the peak index.

This approach ensures we efficiently find the peak element in logarithmic time.

Code

public class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

Time Complexity

• Time Complexity: O(log n) where n is the number of elements in the array. This is because we are using binary search which divides the search space by half each iteration.
• Space Complexity: O(1) since we are using a constant amount of additional space (just a couple of pointers and a mid variable).

This approach is efficient and suitable for large arrays.

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?