algoadvance

Given an array of integers, find all the peak elements. A peak element is an element that is greater than its neighbors. For corner elements, we need to consider only one neighbor. The goal is to return the indices of all the peak elements.

Clarifying Questions

  1. What should be returned if the array is empty?
    • Return an empty list.
  2. What if there are multiple peaks in the array?
    • Return a list of the indices of all the peak elements.
  3. What should be done if all elements are the same?
    • Return indices of all elements as peaks.
  4. Would there be any negative numbers in the array?
    • Yes.
  5. What is the expected input size?
    • This information can help us determine the potential for optimization.

Strategy

  1. Iterate through the array:
    • For each element, check whether it is a peak.
    • Consider the boundaries and edge cases (first and last elements).
  2. Edge cases:
    • For the first element, check if it’s greater than the second element.
    • For the last element, check if it’s greater than the second last element.
  3. Middle elements:
    • Check if each element is greater than both its left and right neighbors.
  4. Collect indices:
    • Maintain a list to collect and return the indices of all peak elements.

Code

from typing import List

def find_peaks(nums: List[int]) -> List[int]:
    if not nums:
        return []
    
    n = len(nums)
    peaks = []
    
    for i in range(n):
        if i == 0:
            # First element, compare to the next element
            if n == 1 or nums[i] > nums[i + 1]:
                peaks.append(i)
        elif i == n - 1:
            # Last element, compare to the previous element
            if nums[i] > nums[i - 1]:
                peaks.append(i)
        else:
            # Middle elements, compare to both neighbors
            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
                peaks.append(i)
                
    return peaks

Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the input array. This is because we are iterating through the array once to check for peak elements.

The space complexity is O(1) auxiliary space, given that we only use a few additional variables besides the input and output storage.

Try our interview co-pilot at AlgoAdvance.com