Explain the Peak and Flag Algorithm

Question

EDIT

Just was pointed that the requirements state peaks cannot be ends of Arrays.

So I ran across this site

http://codility.com/

Which gives you programming problems and gives you certificates if you can solve them in 2 hours. The very first question is one I have seen before, typically called the Peaks and Flags question. If you are not familiar

A non-empty zero-indexed 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. 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 that, given a non-empty zero-indexed array A of N integers, returns the maximum number of flags that can be set on the peaks of the array. For example, given the array above

the function should return 3, as explained above.

Assume that:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [0..1,000,000,000].

Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

So this makes sense, but I failed it using this code

public int GetFlags(int[] A)
{
        List<int> peakList = new List<int>();
        for (int i = 0; i <= A.Length - 1; i++)
        {               
                if ((A[i] > A[i + 1] && A[i] > A[i - 1]))
                {
                    peakList.Add(i);
                }
        }

        List<int> flagList = new List<int>();
        int distance = peakList.Count;
        flagList.Add(peakList[0]);
        for (int i = 1, j = 0, max = peakList.Count; i < max; i++)
        {
            if (Math.Abs(Convert.ToDecimal(peakList[j]) - Convert.ToDecimal(peakList[i])) >= distance)
            {
                flagList.Add(peakList[i]);
                j = i;
            }
        }
        return flagList.Count;
}

EDIT

int[] A = new int[] { 7, 10, 4, 5, 7, 4, 6, 1, 4, 3, 3, 7 };

The correct answer is 3, but my application says 2

This I do not get, since there are 4 peaks (indices 1,4,6,8) and from that, you should be able to place a flag at 2 of the peaks (1 and 6)

Am I missing something here? Obviously my assumption is that the beginning or end of an Array can be a peak, is this not the case?

If this needs to go in Stack Exchange Programmers, I will move it, but thought dialog here would be helpful.

EDIT

Answer 1

I give here my solution of the task that makes 100% score (correctness and performance) in codility, implemented in C++. To understand the solution you must realize for a given distance of indexes (for example, when first peak starts at index 2 and the last peak at index 58 the distance is 56), that contains n peaks there is an upper limit for the maximal number of peaks that can hold flags according to condition described in the task.

#include <vector>
#include <math.h>

typedef unsigned int uint;

void flagPeaks(const std::vector<uint> & peaks,
    std::vector<uint> & flaggedPeaks,
    const uint & minDist)
{
    flaggedPeaks.clear();
    uint dist = peaks[peaks.size() - 1] - peaks[0];
    if (minDist > dist / 2)
        return;

    flaggedPeaks.push_back(peaks[0]);
    for (uint i = 0; i < peaks.size(); ) {
        uint j = i + 1;
        while (j < (peaks.size()) && ((peaks[j] - peaks[i]) < minDist))
            ++j;

        if (j < (peaks.size()) && ((peaks[j] - peaks[i]) >= minDist))
            flaggedPeaks.push_back(peaks[j]);
        i = j;
    }
}


int solution(std::vector<int> & A)
{
    std::vector<uint> peaks;
    uint min = A.size();
    for (uint i = 1; i < A.size() - 1; i++) {
        if ((A[i] > A[i - 1]) && (A[i] > A[i + 1])) {
            peaks.push_back(i);
            if (peaks.size() > 1) {
                if (peaks[peaks.size() - 1] - peaks[peaks.size() - 2] < min)
                    min = peaks[peaks.size() - 1] - peaks[peaks.size() - 2];
            }
        }
    }
    // minimal distance between 2 peaks is 2
    // so when we have less than 3 peaks we are done
    if (peaks.size() < 3 || min >= peaks.size())
        return peaks.size();

    const uint distance = peaks[peaks.size() - 1] - peaks[0];
    // parts are the number of pieces between peaks
    // given n + 1 peaks we always have n parts
    uint parts = peaks.size() - 1;
    // calculate maximal possible number of parts
    // for the given distance and number of peaks
    double avgOptimal = static_cast<double>(distance) / static_cast<double> (parts);
    while (parts > 1 && avgOptimal < static_cast<double>(parts + 1)) {
        parts--;
        avgOptimal = static_cast<double>(distance) / static_cast<double>(parts);
    }

    std::vector<uint> flaggedPeaks;
    // check how many peaks we can flag for the 
    // minimal possible distance between two flags
    flagPeaks(peaks, flaggedPeaks, parts + 1);
    uint flags = flaggedPeaks.size();
    if (flags >= parts + 1)
        return parts + 1;

    // reduce the minimal distance between flags
    // until the condition fulfilled
    while ((parts > 0) && (flags < parts + 1)) {
        --parts;
        flagPeaks(peaks, flaggedPeaks, parts + 1);
        flags = flaggedPeaks.size();
    }
    // return the maximal possible number of flags 
    return parts + 1;
}

Answer 2

Here is a hint: If it is possible to set m flags, then there must be at least m * (m - 1) + 1 array elements. Given that N < 100,000, turning the above around should give you confidence that the problem can be efficiently brute-forced.

No, that is wrong. Codility puts custom solutions through a series of tests, and brute forcing can easily fail on time.

Answer 3

Here is a hint: If it is possible to set m flags, then there must be at least m * (m - 1) + 1 array elements. Given that N < 100,000, turning the above around should give you confidence that the problem can be efficiently brute-forced.

Answer 4

Obviously my assumption is that the beginning or end of an Array can be a peak, is this not the case?

Your assumption is wrong since peak is defined as:

0 < P < N − 1

When it comes to your second example you can set 3 flags on 1, 4, 8.