Tasks Details
medium
1.
Flags
Find the maximum number of flags that can be set on mountain peaks.
Task Score
66%
Correctness
100%
Performance
28%
A non-empty array A consisting of N integers is given.
A peak is an array element which is larger than its neighbours. More precisely, it is an index P such that 0 < P < N − 1 and A[P − 1] < A[P] > A[P + 1].
For example, the following array A:
A[0] = 1 A[1] = 5 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2has exactly four peaks: elements 1, 3, 5 and 10.
You are going on a trip to a range of mountains whose relative heights are represented by array A, as shown in a figure below. You have to choose how many flags you should take with you. The goal is to set the maximum number of flags on the peaks, according to certain rules.
Flags can only be set on peaks. What's more, if you take K flags, then the distance between any two flags should be greater than or equal to K. The distance between indices P and Q is the absolute value |P − Q|.
For example, given the mountain range represented by array A, above, with N = 12, if you take:
- two flags, you can set them on peaks 1 and 5;
- three flags, you can set them on peaks 1, 5 and 10;
- four flags, you can set only three flags, on peaks 1, 5 and 10.
You can therefore set a maximum of three flags in this case.
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty array A of N integers, returns the maximum number of flags that can be set on the peaks of the array.
For example, the following array A:
A[0] = 1 A[1] = 5 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2the function should return 3, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..400,000];
- each element of array A is an integer within the range [0..1,000,000,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Time spent on task 1 minutes
Notes
not defined yet
Code: 14:14:58 UTC,
java,
autosave
Code: 14:15:05 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
List<Integer> peekList = new ArrayList<>();
int maxFlagCount = 0;
for (int i=1; i<A.length-1; i++) {
if (A[i] > A[i-1] && A[i] > A[i+1]) {
peekList.add(i);
i++;
}
}
if (peekList.size() < 3)
return peekList.size();
for (int i=2; i<=peekList.size() && i<=A.length/i+1; i++) {
int count = 1;
int prevIndex = peekList.get(0);
for (int j=1; j<peekList.size() && count<i; j++) {
if (peekList.get(j) - prevIndex >= i) {
count++;
prevIndex = peekList.get(j);
}
}
if (maxFlagCount > count) {
return maxFlagCount;
}
maxFlagCount = Math.max(maxFlagCount, count);
}
return maxFlagCount;
}
}
Code: 14:15:19 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
List<Integer> peekList = new ArrayList<>();
int maxFlagCount = 0;
for (int i=1; i<A.length-1; i++) {
if (A[i] > A[i-1] && A[i] > A[i+1]) {
peekList.add(i);
i++;
}
}
for (int i=2; i<=peekList.size() &&; i++) {
int count = 1;
int prevIndex = peekList.get(0);
for (int j=1; j<peekList.size() && count<i; j++) {
if (peekList.get(j) - prevIndex >= i) {
count++;
prevIndex = peekList.get(j);
}
}
if (maxFlagCount > count) {
return maxFlagCount;
}
maxFlagCount = Math.max(maxFlagCount, count);
}
return maxFlagCount;
}
}
Code: 14:15:35 UTC,
java,
verify,
result: Failed
import java.util.*;
class Solution {
public int solution(int[] A) {
List<Integer> peekList = new ArrayList<>();
for (int i=1; i<A.length-1; i++) {
if (A[i] > A[i-1] && A[i] > A[i+1]) {
peekList.add(i);
i++;
}
}
int maxFlagCount = 0;
for (int i=1; i<=peekList.size() &&; i++) {
int count = 1;
int prevIndex = peekList.get(0);
for (int j=1; j<peekList.size() && count<i; j++) {
if (peekList.get(j) - prevIndex >= i) {
count++;
prevIndex = peekList.get(j);
}
}
maxFlagCount = Math.max(maxFlagCount, count);
}
return maxFlagCount;
}
}
Analysis
Compile error
Solution.java:14: error: illegal start of expression
for (int i=1; i<=peekList.size() &&; i++) {
^
1 error
Code: 14:15:43 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
List<Integer> peekList = new ArrayList<>();
for (int i=1; i<A.length-1; i++) {
if (A[i] > A[i-1] && A[i] > A[i+1]) {
peekList.add(i);
i++;
}
}
int maxFlagCount = 0;
for (int i=1; i<=peekList.size(); i++) {
int count = 1;
int prevIndex = peekList.get(0);
for (int j=1; j<peekList.size() && count<i; j++) {
if (peekList.get(j) - prevIndex >= i) {
count++;
prevIndex = peekList.get(j);
}
}
maxFlagCount = Math.max(maxFlagCount, count);
}
return maxFlagCount;
}
}
Code: 14:15:48 UTC,
java,
verify,
result: Passed
import java.util.*;
class Solution {
public int solution(int[] A) {
List<Integer> peekList = new ArrayList<>();
for (int i=1; i<A.length-1; i++) {
if (A[i] > A[i-1] && A[i] > A[i+1]) {
peekList.add(i);
i++;
}
}
int maxFlagCount = 0;
for (int i=1; i<=peekList.size(); i++) {
int count = 1;
int prevIndex = peekList.get(0);
for (int j=1; j<peekList.size() && count<i; j++) {
if (peekList.get(j) - prevIndex >= i) {
count++;
prevIndex = peekList.get(j);
}
}
maxFlagCount = Math.max(maxFlagCount, count);
}
return maxFlagCount;
}
}
User test case 1:
[1, 3, 2]
Analysis
Code: 14:15:53 UTC,
java,
verify,
result: Passed
import java.util.*;
class Solution {
public int solution(int[] A) {
List<Integer> peekList = new ArrayList<>();
for (int i=1; i<A.length-1; i++) {
if (A[i] > A[i-1] && A[i] > A[i+1]) {
peekList.add(i);
i++;
}
}
int maxFlagCount = 0;
for (int i=1; i<=peekList.size(); i++) {
int count = 1;
int prevIndex = peekList.get(0);
for (int j=1; j<peekList.size() && count<i; j++) {
if (peekList.get(j) - prevIndex >= i) {
count++;
prevIndex = peekList.get(j);
}
}
maxFlagCount = Math.max(maxFlagCount, count);
}
return maxFlagCount;
}
}
User test case 1:
[1, 3, 2]
Analysis
Code: 14:15:58 UTC,
java,
final,
score:
66
import java.util.*;
class Solution {
public int solution(int[] A) {
List<Integer> peekList = new ArrayList<>();
for (int i=1; i<A.length-1; i++) {
if (A[i] > A[i-1] && A[i] > A[i+1]) {
peekList.add(i);
i++;
}
}
int maxFlagCount = 0;
for (int i=1; i<=peekList.size(); i++) {
int count = 1;
int prevIndex = peekList.get(0);
for (int j=1; j<peekList.size() && count<i; j++) {
if (peekList.get(j) - prevIndex >= i) {
count++;
prevIndex = peekList.get(j);
}
}
maxFlagCount = Math.max(maxFlagCount, count);
}
return maxFlagCount;
}
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
expand all
Correctness tests
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.008 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
1.
0.008 s
OK
1.
0.008 s
OK
1.
0.012 s
OK
1.
2.992 s
OK
2.
0.460 s
OK
1.
0.004 s
OK
2.
0.024 s
OK
expand all
Performance tests
large_random
chaotic large sequences, length = ~100,000
chaotic large sequences, length = ~100,000
✘
TIMEOUT ERROR
running time: >7.00 sec., time limit: 1.39 sec.
running time: >7.00 sec., time limit: 1.39 sec.
1.
7.000 s
TIMEOUT ERROR,
running time: >7.00 sec., time limit: 1.39 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.66 sec.
1.
0.276 s
OK
2.
1.260 s
OK
large_many_peaks
large test with 10,000 - 25,000 peaks
large test with 10,000 - 25,000 peaks
✘
TIMEOUT ERROR
running time: >7.00 sec., time limit: 1.15 sec.
running time: >7.00 sec., time limit: 1.15 sec.
1.
7.000 s
TIMEOUT ERROR,
running time: >7.00 sec., time limit: 1.15 sec.
2.
7.000 s
TIMEOUT ERROR,
running time: >7.00 sec., time limit: 1.20 sec.
large_anti_slow
large test anti slow solutions
large test anti slow solutions
✘
TIMEOUT ERROR
running time: >7.00 sec., time limit: 1.92 sec.
running time: >7.00 sec., time limit: 1.92 sec.
1.
7.000 s
TIMEOUT ERROR,
running time: >7.00 sec., time limit: 1.92 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.66 sec.
large_anti_slow2
large test anti slow solutions
large test anti slow solutions
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.66 sec.
running time: >6.00 sec., time limit: 0.66 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.66 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.66 sec.
extreme_max
extreme test, maximal number of elements
extreme test, maximal number of elements
✘
TIMEOUT ERROR
running time: >8.00 sec., time limit: 2.30 sec.
running time: >8.00 sec., time limit: 2.30 sec.
1.
8.000 s
TIMEOUT ERROR,
running time: >8.00 sec., time limit: 2.30 sec.
2.
0.596 s
OK
1.
1.100 s
OK
2.
1.092 s
OK