Divide an array into the maximum number of same-sized blocks, each of which should contain an index P such that A[P - 1] < A[P] > A[P + 1].
- Difficulty Level: Medium
- Question URL: https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/peaks/
- Time Complexity:
Solution:
Solution to Codility's Peaks problem which is from the Codility Lesson 10: Prime and composite numbers and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to divide an array into the maximum number of same-sized blocks, each of which should contain an index p such that a[p - 1] < a[p] > a[p + 1]. You can find the question of this Peaks problem in the Codility website.
package Codility.Lesson10;
import java.util.*;
public class Flags {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a1 = { 1, 5, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2 };
int result2 = solution(a1);
System.out.println(result2);
}
public static int solution(int[] A) {
// write your code in Java SE 8
ArrayList<Integer> peaks = new ArrayList<Integer>();
for (int i = 1; i < A.length - 1; i++) {
if (A[i - 1] < A[i] && A[i + 1] < A[i]) {
peaks.add(i);
}
}
if (peaks.size() <= 1) {
return peaks.size();
}
int maxFlags = (int) Math.ceil(Math.sqrt(peaks.get(peaks.size() - 1) - peaks.get(0)));
for (int flags = maxFlags; flags > 1; flags--) {
int startFlagIndex = 0;
int endFlagIndex = peaks.size() - 1;
int startFlag = peaks.get(startFlagIndex);
int endFlag = peaks.get(endFlagIndex);
int flagsPlaced = 2;
while (startFlagIndex < endFlagIndex) {
startFlagIndex++;
endFlagIndex--;
if (peaks.get(startFlagIndex) >= startFlag + flags) {
if (peaks.get(startFlagIndex) <= endFlag - flags) {
flagsPlaced++;
startFlag = peaks.get(startFlagIndex);
}
}
if (peaks.get(endFlagIndex) >= startFlag + flags) {
if (peaks.get(endFlagIndex) <= endFlag - flags) {
flagsPlaced++;
endFlag = peaks.get(endFlagIndex);
}
}
if (flagsPlaced == flags) {
return flags;
}
}
}
return 0;
}
}