Find the maximum number of flags that can be set on mountain peaks.
- Difficulty Level: Medium
- Question URL: https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/flags/
- Time Complexity:
Solution:
Solution to Codility's Flags 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 find the maximum number of flags that can be set on mountain peaks. You can find the question of this Flags 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;
}
}