1. Introduction
Peak elements within an array are important for numerous algorithms, offering valuable insights into the dataset’s characteristics. In this tutorial, let’s explore the concept of peak elements, explaining their significance and exploring efficient methods to identify them, both in single and multiple peak scenarios.
2. What Is a Peak Element?
A peak element in an array is defined as an element that is strictly greater than its adjacent elements. Edge elements are considered to be in a peak position if they are greater than their only neighboring element.
In scenarios where elements are equal, a strict peak does not exist. Instead, a peak is the first instance where an element exceeds its neighbors.
2.1. Examples
To better understand the idea of peak elements, take a look at the following examples:
Example 1:
List: [1, 2, 20, 3, 1, 0]
Peak Element: 20
Here, 20 is a peak since it is greater than its neighboring elements.
Example 2:
List: [5, 13, 15, 25, 40, 75, 100]
Peak Element: 100
100 is a peak because it’s greater than 75 and has no element to its right.
Example 3:
List: [9, 30, 13, 2, 23, 104, 67, 12]
Peak Element: 30 or 104, as both are valid peaks
Both 30 and 104 qualify as peaks.
3. Finding Single Peak Elements
When an array contains only one peak element, a straightforward approach is to utilize linear search. This algorithm scans through the array elements, comparing each with its neighbors until finding a peak. The time complexity of this method is O(n), where n is the size of the array.
public class SinglePeakFinder {
public static OptionalInt findSinglePeak(int[] arr) {
int n = arr.length;
if (n < 2) {
return n == 0 ? OptionalInt.empty() : OptionalInt.of(arr[0]);
}
if (arr[0] >= arr[1]) {
return OptionalInt.of(arr[0]);
}
for (int i = 1; i < n - 1; i++) {
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) {
return OptionalInt.of(arr[i]);
}
}
if (arr[n - 1] >= arr[n - 2]) {
return OptionalInt.of(arr[n - 1]);
}
return OptionalInt.empty();
}
}
The algorithm iterates through the array from index 1 to n-2, checking if the current element is greater than its neighbors. If a peak is found, an OptionalInt containing the peak is returned. Additionally, the algorithm handles edge cases where the peak is at the extremes of the array.
public class SinglePeakFinderUnitTest {
@Test
void findSinglePeak_givenArrayOfIntegers_whenValidInput_thenReturnsCorrectPeak() {
int[] arr = {0, 10, 2, 4, 5, 1};
OptionalInt peak = SinglePeakFinder.findSinglePeak(arr);
assertTrue(peak.isPresent());
assertEquals(10, peak.getAsInt());
}
@Test
void findSinglePeak_givenEmptyArray_thenReturnsEmptyOptional() {
int[] arr = {};
OptionalInt peak = SinglePeakFinder.findSinglePeak(arr);
assertTrue(peak.isEmpty());
}
@Test
void findSinglePeak_givenEqualElementArray_thenReturnsCorrectPeak() {
int[] arr = {-2, -2, -2, -2, -2};
OptionalInt peak = SinglePeakFinder.findSinglePeak(arr);
assertTrue(peak.isPresent());
assertEquals(-2, peak.getAsInt());
}
}
In the case of bitonic arrays—characterized by a monotonically increasing sequence followed by a monotonically decreasing sequence—the peak can be found more efficiently. By applying a modified binary search technique, we can locate the peak in O(log n) time, significantly reducing the complexity.
It’s important to note that determining whether an array is bitonic requires examination, which, in the worst case, can approach linear time. Therefore, the efficiency gain with the binary search approach is most impactful when the array’s bitonic nature is known.
4. Finding Multiple Peak Elements
Identifying multiple peak elements in an array typically requires examining each element in relation to its neighbors, leading to a linear search algorithm with a time complexity of O(n). This approach ensures no potential peak is overlooked, making it suitable for general arrays.
In specific scenarios, when the array structure allows for segmenting into predictable patterns, modified binary search techniques can be applied to find peaks more efficiently. Let’s use a modified binary search algorithm to achieve a time complexity of O(log n).
Algorithm Explanation:
- Initialize Pointers: Start with two pointers, low and high, representing the range of the array.
- Binary Search: Calculate the middle index mid of the current range.
- Compare Mid with Neighbors: Check if the element at index mid is greater than its neighbors.
- If true, mid is a peak.
- If false, move towards the side with the greater neighbor, ensuring we move towards a potential peak.
- Repeat: Continue the process until the range is reduced to a single element.
public class MultiplePeakFinder {
public static List<Integer> findPeaks(int[] arr) {
List<Integer> peaks = new ArrayList<>();
if (arr == null || arr.length == 0) {
return peaks;
}
findPeakElements(arr, 0, arr.length - 1, peaks, arr.length);
return peaks;
}
private static void findPeakElements(int[] arr, int low, int high, List<Integer> peaks, int length) {
if (low > high) {
return;
}
int mid = low + (high - low) / 2;
boolean isPeak = (mid == 0 || arr[mid] > arr[mid - 1]) && (mid == length - 1 || arr[mid] > arr[mid + 1]);
boolean isFirstInSequence = mid > 0 && arr[mid] == arr[mid - 1] && arr[mid] > arr[mid + 1];
if (isPeak || isFirstInSequence) {
if (!peaks.contains(arr[mid])) {
peaks.add(arr[mid]);
}
}
findPeakElements(arr, low, mid - 1, peaks, length);
findPeakElements(arr, mid + 1, high, peaks, length);
}
}
The MultiplePeakFinder class employs a modified binary search algorithm to identify multiple peak elements in an array efficiently. The findPeaks method initializes two pointers, low and high, representing the range of the array.
It calculates the middle index (mid) and checks if the element at mid is greater than its neighbors. If true, it marks mid as a peak and continues the search in the potential peak-rich region.
public class MultiplePeakFinderUnitTest {
@Test
void findPeaks_givenArrayOfIntegers_whenValidInput_thenReturnsCorrectPeaks() {
MultiplePeakFinder finder = new MultiplePeakFinder();
int[] array = {1, 13, 7, 0, 4, 1, 4, 45, 50};
List<Integer> peaks = finder.findPeaks(array);
assertEquals(3, peaks.size());
assertTrue(peaks.contains(4));
assertTrue(peaks.contains(13));
assertTrue(peaks.contains(50));
}
}
The efficiency of binary search for finding peaks depends on the array’s structure, allowing for peak detection without checking every element. However, without knowing the array’s structure or if it lacks a suitable pattern for binary search, linear search is the most dependable method, guaranteeing no peak is overlooked.
5. Handling Edge Cases
Understanding and addressing edge cases is crucial for ensuring the robustness and reliability of the peak element algorithm.
5.1. Array With No Peaks
In scenarios where the array contains no peak elements, it is essential to indicate this absence. Let’s return an empty array when no peaks are found:
public class PeakElementFinder {
public List<Integer> findPeakElements(int[] arr) {
int n = arr.length;
List<Integer> peaks = new ArrayList<>();
if (n == 0) {
return peaks;
}
for (int i = 0; i < n; i++) {
if (isPeak(arr, i, n)) {
peaks.add(arr[i]);
}
}
return peaks;
}
private boolean isPeak(int[] arr, int index, int n) {
return arr[index] >= arr[index - 1] && arr[index] >= arr[index + 1];
}
}
The findPeakElement method iterates through the array, utilizing the isPeak helper function to identify peaks. If no peaks are found, it returns an empty array.
public class PeakElementFinderUnitTest {
@Test
void findPeakElement_givenArrayOfIntegers_whenValidInput_thenReturnsCorrectPeak() {
PeakElementFinder finder = new PeakElementFinder();
int[] array = {1, 2, 3, 2, 1};
List<Integer> peaks = finder.findPeakElements(array);
assertEquals(1, peaks.size());
assertTrue(peaks.contains(3));
}
@Test
void findPeakElement_givenArrayOfIntegers_whenNoPeaks_thenReturnsEmptyList() {
PeakElementFinder finder = new PeakElementFinder();
int[] array = {};
List<Integer> peaks = finder.findPeakElements(array);
assertEquals(0, peaks.size());
}
}
5.2. Array With Peaks at Extremes
When peaks exist at the first or last element, special consideration is necessary to avoid undefined neighbor comparisons. Let’s add a conditional check in the isPeak method to handle these cases:
private boolean isPeak(int[] arr, int index, int n) {
if (index == 0) {
return n > 1 ? arr[index] >= arr[index + 1] : true;
} else if (index == n - 1) {
return arr[index] >= arr[index - 1];
}
return arr[index] >= arr[index - 1] && arr[index] >= arr[index + 1];
}
This modification ensures that peaks at the extremes are correctly identified without attempting comparisons with undefined neighbors.
public class PeakElementFinderUnitTest {
@Test
void findPeakElement_givenArrayOfIntegers_whenPeaksAtExtremes_thenReturnsCorrectPeak() {
PeakElementFinder finder = new PeakElementFinder();
int[] array = {5, 2, 1, 3, 4};
List<Integer> peaks = finder.findPeakElements(array);
assertEquals(2, peaks.size());
assertTrue(peaks.contains(5));
assertTrue(peaks.contains(4));
}
}
5.3. Dealing With Plateaus (Consecutive Equal Elements)
In cases where the array contains consecutive equal elements, returning the index of the first occurrence is crucial. The isPeak function handles this by skipping consecutive equal elements:
private boolean isPeak(int[] arr, int index, int n) {
if (index == 0) {
return n > 1 ? arr[index] >= arr[index + 1] : true;
} else if (index == n - 1) {
return arr[index] >= arr[index - 1];
} else if (arr[index] == arr[index + 1] && arr[index] > arr[index - 1]) {
int i = index;
while (i < n - 1 && arr[i] == arr[i + 1]) {
i++;
}
return i == n - 1 || arr[i] > arr[i + 1];
} else {
return arr[index] >= arr[index - 1] && arr[index] >= arr[index + 1];
}
}
The findPeakElement function skips consecutive equal elements, ensuring that the index of the first occurrence is returned when identifying peaks.
public class PeakElementFinderUnitTest {
@Test
void findPeakElement_givenArrayOfIntegers_whenPlateaus_thenReturnsCorrectPeak() {
PeakElementFinder finder = new PeakElementFinder();
int[] array = {1, 2, 2, 2, 3, 4, 5};
List<Integer> peaks = finder.findPeakElements(array);
assertEquals(1, peaks.size());
assertTrue(peaks.contains(5));
}
}
6. Conclusion
Understanding the techniques to find peak elements enables developers to make informed decisions when designing efficient and resilient algorithms. There are various approaches to discovering peak elements, with methods offering different time complexities, such as O(log n) or O(n).
The selection among these methods depends on specific requirements and application constraints. Choosing the right algorithm aligns with the efficiency and performance goals aimed to achieve in the application.
You can find all the code samples over on GitHub.