CODEWITHSUNDEEP
javascript
Saito Asuka
Saito Asuka

Reputation: 300

80% Javascript Solution for Flags in Codility

Flags, the famous code challenge in Codility.

I've tried several times and I'm pretty sure the bug is inside the function "CheckFlags" I've also tried the official solution provided by Codility and got 100% eventually. However, I cannot figure out why my checking algorithm fails and there are only three failed test data (check test report). 

function solution(A) {

    let peakIndex = [];
    let peakCount = 0;

    for (let i = 1; i < A.length-1; i++) {
        if (A[i-1] < A[i] && A[i] > A[i+1]) {
            peakIndex[peakCount] = i;
            peakCount++;
        }
    }

    if (peakCount === 0 || peakCount === 1) 
        return peakCount;


    let left = 2;
    let right = peakCount;
    let result;

    while(right >= left) { // binary search

        let flags = Math.floor((left+right)/2)

        if (!CheckFlags(peakIndex, flags)) {
            right = flags - 1;    
        } else {
            result = flags;
            left = flags + 1;
        }
    }

    return result;
}

function CheckFlags (peakIndex, flags) {

    let flagCount = 1;
    let flagIndex = new Array(flags);
    flagIndex[0] = 0; // always include the first flag

    for (let peakIter = 1; peakIter < peakIndex.length && flagCount <= flags; peakIter++) {
        if (peakIndex[peakIter] - flagIndex[flagCount - 1] >= flags) {
            flagIndex[flagCount] = peakIndex[peakIter];
            flagCount++;

            if (flagCount === flags) 
                return true;
        }
    }

    return false;
}

Upvotes: 0

Views: 1033

Answers (1)

Tom Price
Tom Price

Reputation: 147

The problem is in the line 

flagIndex[0] = 0;

This line of code sets the location for the first flag index, but incorrectly assigns the first location instead of the location of the first peak. It should read

flagIndex[0] = peakIndex[0];

Upvotes: 2

Related Questions