Jobs

Interviews

Discussions

Find Peak Element

Medium

Amazon

5 views

Topics:

ArraysBinary Search

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1
nums[i] != nums[i + 1] for all valid i.

Find Peak Element

Medium

Amazon

5 views

Topics:

ArraysBinary Search

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1
nums[i] != nums[i + 1] for all valid i.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the integers in the array? Can they be negative, zero, or very large?
Is the array guaranteed to have at least one element?
If there are multiple peak elements, is there a preference as to which index I should return? If not, can I return any peak?
If `nums` has only one element, is that element considered a peak?
Can two adjacent elements be equal? If `nums[i] == nums[i+1]`, is it still guaranteed that a peak exists?

Brute Force Solution

Approach

We're trying to find a value that is larger than its neighbors. The brute force approach simply checks every single value to see if it fits the criteria.

Here's how the algorithm would work step-by-step:

Start with the very first value.
Check if this value is bigger than the value next to it. If there isn't one next to it, assume it's smaller than it.
Move to the next value.
Check if this value is bigger than the values on either side of it. If there is no value on one of the sides, assume it is smaller than it.
Keep going through all the values, repeating this check.
The first value you find that's bigger than both of its neighbors is your answer.

Code Implementation

def find_peak_element_brute_force(numbers):
    for index in range(len(numbers)):
        # Check if the current element is greater than the next element
        if index == len(numbers) - 1:
            next_element = float('-inf')
        else:
            next_element = numbers[index + 1]

        # Check if the current element is greater than the previous element
        if index == 0:
            previous_element = float('-inf')

        else:
            previous_element = numbers[index - 1]

        # If both neighbors are smaller, then we found the peak
        if numbers[index] > next_element and numbers[index] > previous_element:
            return index

    return -1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n elements in the input array. For each element, it performs a constant amount of work: comparing the element to its immediate neighbor(s). Therefore, the time complexity is directly proportional to the number of elements, resulting in O(n) time complexity.

Space Complexity

O(1) – The provided algorithm iterates through the input array and compares each element with its neighbors. It doesn't create any additional data structures like lists, dictionaries, or sets to store intermediate results. The space used is limited to a few variables for indexing and comparison, regardless of the input array's size (N). Therefore, the space complexity remains constant.

Optimal Solution

Approach

The goal is to quickly find a peak in a set of numbers. Instead of checking every number, which would take a long time, we use a divide-and-conquer strategy to zoom in on the peak efficiently.

Here's how the algorithm would work step-by-step:

Start by looking at the middle number in the set.
Compare the middle number to the numbers on either side of it.
If the middle number is bigger than both its neighbors, you've found a peak, and you're done.
If the number to the left of the middle number is bigger, you know a peak must exist somewhere in the left half of the set. So, focus only on the left half.
If the number to the right of the middle number is bigger, a peak must be in the right half. Focus only on the right half.
Repeat this process of checking the middle and narrowing your focus to either the left or right until you find a peak.

Code Implementation

def find_peak_element(numbers):
    left_index = 0
    right_index = len(numbers) - 1

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # Check if the middle element is a peak.
        if numbers[middle_index] > numbers[middle_index + 1]:
            # If middle is greater, peak is in left half.
            right_index = middle_index

        else:
            # Peak is in the right half.
            left_index = middle_index + 1

    # At the end of the search, leftIndex is the peak.
    return left_index

Big(O) Analysis

Time Complexity

O(log n) – The algorithm employs a binary search approach to find the peak element within an array of size n. In each iteration, the search space is halved by comparing the middle element with its neighbors. This halving continues until a peak is found or the search space is reduced to a single element. Therefore, the number of iterations required is proportional to the logarithm base 2 of n, resulting in a time complexity of O(log n).

Space Complexity

O(log N) – The algorithm employs a divide-and-conquer approach, effectively halving the search space in each step. This process is primarily implemented through recursive calls. The maximum depth of these recursive calls corresponds to the number of times the input can be halved until we reach a single element. Thus, the space complexity is determined by the recursion depth, which is logarithmic with respect to the input size N, where N is the number of elements in the set.

Edge Cases

Case	How to Handle
Empty or null input array	Return -1 immediately since no peak can exist in an empty array.
Array with only one element	Return index 0, as a single element is trivially a peak.
Array with two elements, one larger than other	Return index of larger element, the larger of the two will be peak.
Peak at the beginning of the array (index 0)	The algorithm should correctly identify the peak if nums[0] > nums[1].
Peak at the end of the array (index nums.length - 1)	The algorithm should correctly identify the peak if nums[nums.length - 1] > nums[nums.length - 2].
Array with all elements equal	Return index 0, as any element can be considered a peak if neighbors are equal.
Large array where elements are sorted in ascending order	Binary search approach is efficient for large arrays, but needs adjustment when there is no peak (i.e., strictly increasing).
Negative numbers in the array	The comparison logic should work correctly with negative numbers without modification.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the integers in the array? Can they be negative, zero, or very large?
Is the array guaranteed to have at least one element?
If there are multiple peak elements, is there a preference as to which index I should return? If not, can I return any peak?
If `nums` has only one element, is that element considered a peak?
Can two adjacent elements be equal? If `nums[i] == nums[i+1]`, is it still guaranteed that a peak exists?

Brute Force Solution

Approach

We're trying to find a value that is larger than its neighbors. The brute force approach simply checks every single value to see if it fits the criteria.

Here's how the algorithm would work step-by-step:

Start with the very first value.
Check if this value is bigger than the value next to it. If there isn't one next to it, assume it's smaller than it.
Move to the next value.
Check if this value is bigger than the values on either side of it. If there is no value on one of the sides, assume it is smaller than it.
Keep going through all the values, repeating this check.
The first value you find that's bigger than both of its neighbors is your answer.

Code Implementation

def find_peak_element_brute_force(numbers):
    for index in range(len(numbers)):
        # Check if the current element is greater than the next element
        if index == len(numbers) - 1:
            next_element = float('-inf')
        else:
            next_element = numbers[index + 1]

        # Check if the current element is greater than the previous element
        if index == 0:
            previous_element = float('-inf')

        else:
            previous_element = numbers[index - 1]

        # If both neighbors are smaller, then we found the peak
        if numbers[index] > next_element and numbers[index] > previous_element:
            return index

    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to quickly find a peak in a set of numbers. Instead of checking every number, which would take a long time, we use a divide-and-conquer strategy to zoom in on the peak efficiently.

Here's how the algorithm would work step-by-step:

Start by looking at the middle number in the set.
Compare the middle number to the numbers on either side of it.
If the middle number is bigger than both its neighbors, you've found a peak, and you're done.
If the number to the left of the middle number is bigger, you know a peak must exist somewhere in the left half of the set. So, focus only on the left half.
If the number to the right of the middle number is bigger, a peak must be in the right half. Focus only on the right half.
Repeat this process of checking the middle and narrowing your focus to either the left or right until you find a peak.

Code Implementation

def find_peak_element(numbers):
    left_index = 0
    right_index = len(numbers) - 1

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # Check if the middle element is a peak.
        if numbers[middle_index] > numbers[middle_index + 1]:
            # If middle is greater, peak is in left half.
            right_index = middle_index

        else:
            # Peak is in the right half.
            left_index = middle_index + 1

    # At the end of the search, leftIndex is the peak.
    return left_index

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return -1 immediately since no peak can exist in an empty array.
Array with only one element	Return index 0, as a single element is trivially a peak.
Array with two elements, one larger than other	Return index of larger element, the larger of the two will be peak.
Peak at the beginning of the array (index 0)	The algorithm should correctly identify the peak if nums[0] > nums[1].
Peak at the end of the array (index nums.length - 1)	The algorithm should correctly identify the peak if nums[nums.length - 1] > nums[nums.length - 2].
Array with all elements equal	Return index 0, as any element can be considered a peak if neighbors are equal.
Large array where elements are sorted in ascending order	Binary search approach is efficient for large arrays, but needs adjustment when there is no peak (i.e., strictly increasing).
Negative numbers in the array	The comparison logic should work correctly with negative numbers without modification.