Peak and Flag Codility latest chellange

Question

I'm trying to solve the latest codility.com question (just for enhance my skills). I tried allot but not getting more than 30 marks there so now curious what exactly I am missing in my solution.

The question says

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).

So I tried this code according to my understanding of question

var A = [1,5,3,4,3,4,1,2,3,4,6,2];

function solution(A) {
 array = new Array();  
   for (i = 1; i < A.length - 1; i++) {  
    if (A[i - 1] < A[i] && A[i + 1] < A[i]) {  
     array.push(i);  
    }  
   }  

  //console.log(A);
  //console.log(array);
  var position = array[0];
  var counter = 1;
  var len = array.length;
  for (var i = 0; i < len; i++) {
    if (Math.abs(array[i+1] - position) >= len) {
        position = array[i+1];
        counter ++;
        }
    }

  console.log("total:",counter);
  return counter;

}

The above code works for sample array elements: [1,5,3,4,3,4,1,2,3,4,6,2] Get peaks at indices: [1, 3, 5, 10] and set flags at 1, 5, and 10 (total 3)

But codility.com says it fails on array [7, 10, 4, 5, 7, 4, 6, 1, 4, 3, 3, 7] My code get peaks at indices: [1, 4, 6, 8] and set flags at 1 and 6 (total 2) but coditity.com says it should be 3 flags. (no idea why) Am I miss-understanding the question ?

Please I am only looking for the hint/algo. I know this question is already asked by someone and solved on private chatroom but on that page I tried to get the help with that person but members rather flagging my posts as inappropriate answer so I am asking the question here again.

P.S: You can try coding the challenge yourself here!

Answer 1

100% Java solution with O(N) complexity.

https://app.codility.com/demo/results/trainingPNYEZY-G6Q/

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int[] peaks = new int[A.length];
        int peakStart = 0;
        int peakEnd = 0;
        
        //Find the peaks.
        //We don't want to traverse the array where peaks hasn't started, yet, 
        //or where peaks doesn't occur any more.
        //Therefore, find start and end points of the peak as well.
        for(int i = 1; i < A.length-1; i++) {
            if(A[i-1] < A[i] && A[i+1] < A[i]) {
                peaks[i] = 1;
                peakEnd = i + 1;
            }
            if(peakStart == 0) {
                peakStart = i;
            }
        }
        
        int x = 1;
        //The maximum number of flags can be √N
        int limit = (int)Math.ceil(Math.sqrt(A.length));
        int prevPeak = 0;
        int counter = 0;
        int max = Integer.MIN_VALUE;
        
        while(x <= limit) {
            counter = 0;
            prevPeak = 0;
            for(int y = peakStart; y < peakEnd; y++) {
                //Find the peak points when we have x number of flags.
                if(peaks[y] == 1 && (prevPeak == 0 || x <= (y - prevPeak))) {
                    counter++;
                    prevPeak = y;
                }
                //If we don't have any more flags stop.
                if(counter == x ) {
                    break;
                }
            }
            //if the number of flags set on the peaks starts to reduce stop searching.
            if(counter <= max) {
                return max;
            }
            //Keep the maximum number of flags we set on.
            max = counter;
            x++;
        }
        return max;
    }
}

• There is a ratio between the number of flags we can take with us and the number of flags we can set. We can not set more than √N number of flags since N/√N = √N. If we set more than √N, we will end up with decreasing number of flags set on the peaks.

• When we increase the numbers of flags we take with us, the number of flags we can set increases up to a point. After that point the number of flags we can set will decrease. Therefore, when the number of flags we can set starts to decrease once, we don't have to check the rest of the possible solutions.

• We mark the peak points at the beginning of the code, and we also mark the first and the last peak points. This reduces the unnecessary checks where the peaks starts at the very last elements of a large array or the last peak occurs at the very first elements of a large array.

Answer 2

This is a solution with better upper complexity bounds:

• time complexity: O(sqrt(N) * log(N))
• space complexity: O(1) (over the original input storage)

Python implementation

from math import sqrt

def transform(A):
    peak_pos = len(A)
    last_height = A[-1]
    for p in range(len(A) - 1, 0, -1):
        if (A[p - 1] < A[p] > last_height):
            peak_pos = p
        last_height = A[p]
        A[p] = peak_pos
    A[0] = peak_pos

def can_fit_flags(A, k):
    flag = 1 - k
    for i in range(k):
        # plant the next flag at A[flag + k]
        if flag + k > len(A) - 1:
            return False
        flag = A[flag + k]
    return flag < len(A)  # last flag planted successfully

def solution(A):
    transform(A)
    lower = 0
    upper = int(sqrt(len(A))) + 2
    assert not can_fit_flags(A, k=upper)
    while lower < upper - 1:
        next = (lower + upper) // 2
        if can_fit_flags(A, k=next):
            lower = next
        else:
            upper = next
    return lower

Description

O(N) preprocessing (done inplace):

A[i] := next peak or end position after or at position i
        (i for a peak itself, len(A) after last peak)

If we can plant k flags then we can certainly plant k' < k flags as well. If we can not plant k flags then we certainly can not plant k' > k flags either. We can always set 0 flags. Let us assume we can not set X flags. Now we can use binary search to find out exactly how many flags can be planted.

Steps:
  1. X/2
  2. X/2 +- X/4
  3. X/2 +- X/4 +- X/8
  ...
  log2(X) steps in total

With the preprocessing done before, each step testing whether k flags can be planted can be performed in O(k) operations:

• flag(0) = next(0)
• flag(1) = next(flag(1) + k) ...
• flag(k-1) = next(flag(k-2) + k)

total cost - worst case - when X - 1 flags can be planted:

== X * (1/2 + 3/4 + ... + (2^k - 1)/(2^k))
== X * (log2(X) - 1 + (<1))
<= X * log(X)

Using X == N would work, and would most likely also be sublinear, but is not good enough to use in a proof that the total upper bound for this algorithm is under O(N).

Now everything depends on finding a good X, and it since k flags take about k^2 positions to fit, it seems like a good upper limit on the number of flags should be found somewhere around sqrt(N).

If X == sqrt(N) or something close to it works, then we get an upper bound of O(sqrt(N) * log(sqrt(N))) which is definitely sublinear and since log(sqrt(N)) == 1/2 * log(N) that upper bound is equivalent to O(sqrt(N) * log(N)).

Let's look for a more exact upper bound on the number of required flags around sqrt(N):

• we know k flags requires Nk := k^2 - k + 3 flags
• by solving the equation k^2 - k + 3 - N = 0 over k we find that if k >= 3, then any number of flags <= the resulting k can fit in some sequence of length N and a larger one can not; solution to that equation is 1/2 * (1 + sqrt(4N - 11))
• for N >= 9 we know we can fit 3 flags ==> for N >= 9, k = floor(1/2 * (1 + sqrt(4N - 11))) + 1 is a strict upper bound on the number of flags we can fit in N
• for N < 9 we know 3 is a strict upper bound but those cases do not concern us for finding the big-O algorithm complexity

floor(1/2 * (1 + sqrt(4N - 11))) + 1
== floor(1/2 + sqrt(N - 11/4)) + 1
<= floor(sqrt(N - 11/4)) + 2
<= floor(sqrt(N)) + 2

==> floor(sqrt(N)) + 2 is also a good strict upper bound for a number of flags that can fit in N elements + this one holds even for N < 9 so it can be used as a generic strict upper bound in our implementation as well

If we choose X = floor(sqrt(N)) + 2 we get the following total algorithm upper bound:

O((floor(sqrt(N)) + 2) * log(floor(sqrt(N)) + 2))
   {floor(...) <= ...}
O((sqrt(N) + 2) * log(sqrt(N) + 2))
   {for large enough N >= 4: sqrt(N) + 2 <= 2 * sqrt(N)}
O(2 * sqrt(N) * log(2 * sqrt(N)))
   {lose the leading constant}
O(sqrt(N) * (log(2) + loq(sqrt(N)))
O(sqrt(N) * log(2) + sqrt(N) * log(sqrt(N)))
   {lose the lower order bound}
O(sqrt(N) * log(sqrt(N)))
   {as noted before, log(sqrt(N)) == 1/2 * log(N)}
O(sqrt(N) * log(N))
                                  QED

Answer 3

Missing 100% PHP solution :)

function solution($A)
{
    $p = array(); // peaks
    for ($i=1; $i<count($A)-1; $i++)
        if ($A[$i] > $A[$i-1] && $A[$i] > $A[$i+1])
            $p[] = $i;

    $n = count($p);
    if ($n <= 2)
        return $n;

    $maxFlags = min(intval(ceil(sqrt(count($A)))), $n); // max number of flags
    $distance = $maxFlags; // required distance between flags
    // try to set max number of flags, then 1 less, etc... (2 flags are already set)
    for ($k = $maxFlags-2; $k > 0; $k--)
    {
        $left = $p[0];
        $right = $p[$n-1];
        $need = $k; // how many more flags we need to set

        for ($i = 1; $i<=$n-2; $i++)
        {
            // found one more flag for $distance
            if ($p[$i]-$left >= $distance && $right-$p[$i] >= $distance)
            {
                if ($need == 1)
                    return $k+2;
                $need--;
                $left = $p[$i];
            }

            if ($right - $p[$i] <= $need * ($distance+1))
                break; // impossible to set $need more flags for $distance
        }

        if ($need == 0)
            return $k+2;

        $distance--;
    }
    return 2;
}

Answer 4

import java.util.Arrays;
import java.lang.Integer;
import java.util.ArrayList;
import java.util.List;
public int solution(int[] A) 
{
    ArrayList<Integer> array = new ArrayList<Integer>();  
        for (int i = 1; i < A.length - 1; i++) 
        {  
            if (A[i - 1] < A[i] && A[i + 1] < A[i]) 
            {  
                array.add(i);  
            }  
        }  
   if (array.size() == 1 || array.size() == 0) 
   {  
        return array.size();  
   }  
    int sf = 1;  
    int ef = array.size();  
    int result = 1;  
    while (sf <= ef) 
    {  
        int flag = (sf + ef) / 2;  
        boolean suc = false;  
        int used = 0;  
        int mark = array.get(0);  
        for (int i = 0; i < array.size(); i++) 
        {  
            if (array.get(i) >= mark) 
            {  
                used++;  
                mark = array.get(i) + flag;  
                    if (used == flag) 
                    {                       
                        suc = true;  
                        break;  
                    }  
            }  
        }  
        if (suc) 
        {  
            result = flag;  
            sf = flag + 1;  
        } 
        else 
        {  
            ef = flag - 1;  
        }  
    }  
   return result;  
 }