Codility Peak JavaScript Implementation

Question

I am working on the Codility Peak problem:

Divide an array into the maximum number of same-sized blocks, each of which should contain an index P such that A[P - 1] < A[P] > A[P + 1].

My own solution is provided below, but it only scores 45%. So my question is:

How can I still improve my solution?

The code snippet seems to be long, since I added some extra comments to make myself clearer:

function solution(A) {
  var storage = [], counter = 0;
  // 1. So first I used a loop to find all the peaks
  // and stored them all into an array called storage
  for(var i = 1; i < A.length - 1; i++) {
    if (A[i] > A[i-1] && A[i] > A[i+1]) {
        storage.push(i);
    }
  }
  // 2. Go and write the function canBeSeparatedInto
  // 3. Use the for loop to check the counter
  for(var j = 1; j < A.length; j++) {
    if (canBeSeparatedInto(j, A, storage)) {
      counter = j;
    }
  }
  return counter;
}

/* this function tells if it is possible to divide the given array into given parts
 * we will be passing our function with parameters: 
 * @param parts[number]: number of parts that we intend to divide the array into
 * @param array[array]: the original array
 * @param peaks[array]: an storage array that store all the index of the peaks
 * @return [boolean]: true if the given array can be divided into given parts
 */
function canBeSeparatedInto(parts, array, peaks) {
    var i = 1, result = false;
    var blockSize = array.length / parts;
    peaks.forEach(function(elem) {
    // test to see if there is an element in the array belongs to the ith part
        if ((elem+1)/blockSize <= i && (elem+1)/blockSize> i-1) {
            i++;
        }
    });
    // set the result to true if there are indeed peaks for every parts
    if (i > parts) {
        result = true;
    }
    return result;
}

The main problem with my code is that it does not pass the performance test. Could you give me some hint on that?

Answer 1

I would suggest this algorithm:

• Sort the peeks by the distance they have with their predecessor. To do that, it might be more intuitive to identify "valleys", i.e. maximised ranges without peeks, and sort those by their size in descending order

• Identify the divisors of the array length, as the solution must be one of those. For example, it is a waste of time to test for solutions when the array length is prime: in that case the answer can only be 1 (or zero if it has no peeks).

• Try each of the divisors in ascending order (representing the size of array chunks), and see if for each valley such a split would bring one of the chunks completely inside that valley, i.e. it would not contain a peek: in that case reject that size as a solution, and try the next size.

Implementation with interactive input of the array:

"use strict";
// Helper function to collect the integer divisors of a given n
function divisors(n) {
    var factors = [], 
        factors2 = [],
        sq = Math.sqrt(n);
    for (var i = 1; i <= sq; i++) {
        if (n % i === 0) {
            factors.push(n / i);
            // Save time by storing complementary factor as well
            factors2.push(i);
        }
    }
    // Eliminate possible duplicate when n is a square
    if (factors[factors.length-1] === factors2[factors2.length-1]) factors.pop();
    // Return them sorted in descending order, so smallest is at end
    return factors.concat(factors2.reverse());
}

function solution(A) {
    var valleys = [],
        start = 0,
        size, sizes, i;
    // Collect the maximum ranges that have no peeks
    for (i = 1; i < A.length - 1; i++) {
        if (A[i] > A[i-1] && A[i] > A[i+1]) {
            valleys.push({
                start,
                end: i,
                size: i - start,
            });
            start = i + 1;
        }
    }
    // Add final valley
    valleys.push({
        start,
        end: A.length,
        size: A.length - start 
    });
    if (valleys.length === 1) return 0; // no peeks = no solution
    // Sort the valleys by descending size 
    // to improve the rest of the algorithm's performance
    valleys.sort( (a, b) => b.size - a.size );
    // Collect factors of n, as all chunks must have same, integer size
    sizes = divisors(A.length)
    // For each valley, require that a solution must not 
    // generate a chunk that falls completely inside it
    do {
        size = sizes.pop(); // attempted solution (starting with small size)
        for (i = 0;
            i < valleys.length &&
            // chunk must not fit entirely inside this valley
            Math.ceil(valleys[i].start / size) * size + size > valleys[i].end; i++) {
        }
    } while (i < valleys.length); // keep going until all valleys pass the test
    // Return the number of chunks
    return A.length / size;
}

// Helper function: chops up a given array into an  
//   array of sub arrays, which all have given size, 
//   except maybe last one, which could be smaller.
function chunk(arr, size) {
    var chunks = [];
    for (var i = 0; i < arr.length; i += size) {
        chunks.push(arr.slice(i, i + size));
    }
    return chunks;
}

// I/O management
inp.oninput = function () {
    // Get input as an array of positive integers (ignore non-digits)
    if (!this.value) return;
    var arr = this.value.match(/\d+/g).map(v => +v);
    var parts = solution(arr);
    // Output the array, chopped up into its parts:
    outCount.textContent = parts;
    outChunks.textContent = chunk(arr, arr.length / parts).join('\n');
}

Array (positive integers, any separator): <input id="inp" style="width:100%">
Chunks: <span id="outCount"></span>
<pre id="outChunks"></pre>

Answer 2

When checking whether array can be splitted into K parts, you will in worst case (array of [1,2,1,2,1,...]) do N/2 checks (since you are looking at every peak).

This can be done in K steps, by using clever datastructures: Represent peaks as an binary array (0 - no peak, 1 - peak). Calculate prefix sums over that. If you want to check if block contains a peak, just compare prefix sums at the start and end of the block.

And also you have small other problem there. You should not check number of block which does not divide the size of the array.