Straight Developer

Find the maximum number of flags that can be set on mountain peaks.

“Flags” is the third task of the prime and composite numbers lesson serie on Codility.com, tagged with the flag “respectable” this task is harder than its previous CountFactors and in this article I am going to share with you my solution which has a score of 100% in matter of corectness and performance but before we elaborate the solution here’s the task description on Codility.com:

Codility.com Flags task description

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] = 2

has 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:

function solution(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] = 2

the 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].

Flags task 100% solution in javascript

first step would be to form an array that will contain the position of each peak, so you basically iterate on the array A and test whether a value is greater than the previous and the next value at the same time, then push it into the peaks array if it is the case, once the peaks array is filled then comes the most challenging part which is to calculate the number of flags that we can put on the peaks.
Remember. The distance between each two flags shouldn’t be lower than the total number of flags. Which means that the number of flags is determined by the distances between the peaks so there lays our solution.
Since we can determine what’s the whole distance between the first and the last peak then we know for a fact that the number of flags cannot exceed a certain number. If we take the same example as the task description, this should be the content for the array of peaks:

[ 1, 3, 5, 10]

the total distance here is 9 which is the difference between the value of the last and the first element of the array ( last minus first). knowing this, we can assume that the flags number will never exceed 3. Because if that happens then the total distance will be more than 9 which is impossible. For example, if I give you 4 flags and asked you to start from 1 then put them one after another but without breaking the rule : keep a distance of 4 between each two flags. You’ll obtain this configuration of flags: [1, 5, 9, 14] and as you can see the final element 14 is greater than the farest peak from our array: 9 which makes 4 an impossible value for k (the number of flags).
That being said, in order to calculate the maximum value for k we just need to calculate the square root of the distance between the first and the last peak just as follows:

var root=Math.floor(Math.sqrt(peaks[peaks.length-1]-peaks[0]))

Then we iterate on the peaks but starting from the square root then going down until we obtain the maximum number of the flags that can be placed on the peaks.
Here’s the full solution:

function solution(A) {
    var peaks=[]
    for(var i=1;i<A.length-1;i++){
        if(A[i-1]<A[i] && A[i]>A[i+1])
        peaks.push(i)
    }
    if(peaks.length<2)
    return peaks.length
    var root=Math.floor(Math.sqrt(peaks[peaks.length-1]-peaks[0]))
    for(i=root+1;i>0;i--){
        var distanceSum=0
        var flags=1
        for(var j=0;j<peaks.length-1;j++){
            var current=peaks[j]
            var next=peaks[j+1]
            var difference=Math.abs(next-current)
            if((difference+distanceSum)>=i){
                flags++
                distanceSum=0
            }
            else
            distanceSum+=difference
        if(flags==i)
        return flags
        }
    }
}

The solution is getting 100% score but I feel like there’s a better approach then this but I honestly couldn’t think of it. if by chance you happen to have a better solution then don’t hesitate to share it with me !