Monotonic arrays
are sorted in ascending
or descending
order such as
1, 2, 3, 4, 5 or 5, 4, 3, 2, 1
Bitonic
or Mountain
arrays have elements in ascending
order and then descending
order such as
0, 1
, 0 here 1
is the peak element
1, 2, 3, 4, 5
, 4, 3, 2, 1 here 5
is the peak element
K Sorted Mountain Array
have multiple Monotonic
arrays upto K
times such as
0, 1
, 0, 2
, 0, 4
, 0, 6
, 0 here 1
,2
,4
and 6
are peak elements
1, 2
, 1, 3, 5, 6
, 4 here 2
and 6
both are peak element
The Algorithm is simple
- keep running the loop until the start index is greater than the end index
- if the mid element is greater than its next updated end index, else update the start index.
- in the end, the start and end indexes will point to the largest number.
package org.wesome.dsalgo;
public class KSortedMountainArray {
public static int peakInKSortedMountainArray(int[] arr) {
int start = 0, end = arr.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
// if the middle element is greater than its next element, it means its decreasing part of the array
if (arr[mid] > arr[mid + 1]) {
// mid might be the array's peak, but there is a possibility that an even higher peak may lie on the left sub-array. so keep the mid also, that's why the end is not equal to mid-1
end = mid;
}
// else middle element is less than its next element, it means its increasing part of the array
else {
// in the above if condition, it already checked that mid-element is greater than mid+1, so we don't need to keep mid anymore, hence start will be mid+1
start = mid + 1;
}
}
// in the end, the start index and end index both will point to the largest number
return arr[start];
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import static org.wesome.dsalgo.KSortedMountainArray.peakInKSortedMountainArray;
public class KSortedMountainArrayTest {
@Test
void peakInKSortedMountainArrayTest1() {
int[] arr = new int[]{0, 1, 0, 2, 0, 4, 0, 6, 0};
int peakInKSortedMountainArray = peakInKSortedMountainArray(arr);
Assertions.assertEquals(6, peakInKSortedMountainArray);
}
@Test
void peakInKSortedMountainArrayTest2() {
int[] arr = new int[]{1, 2, 3, 4, 5, 4, 3, 2, 1};
int peakInKSortedMountainArray = peakInKSortedMountainArray(arr);
Assertions.assertEquals(5, peakInKSortedMountainArray);
}
@Test
void peakInKSortedMountainArrayTest3() {
int[] arr = new int[]{1, 3, 5, 7, 6, 4, 2, 0};
int peakInKSortedMountainArray = peakInKSortedMountainArray(arr);
Assertions.assertEquals(7, peakInKSortedMountainArray);
}
@Test
void peakInKSortedMountainArrayTest4() {
int[] arr = new int[]{1, 2, 1, 3, 5, 6, 4};
int peakInKSortedMountainArray = peakInKSortedMountainArray(arr);
Assertions.assertEquals(6, peakInKSortedMountainArray);
}
}
plugins {
id 'java'
id "io.freefair.lombok" version "6.4.1"
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}