Problem

Codility MaxCounters

We are given a number n and an array A of length m where each value in A is less than n+1 and greater than or equal to 1.

We have to create a function that executes two operations using a new array of length n with initial values 0.

The array A is a list of operations that we need to execute on our output array. The value indicates the 1 based index of the result array to increment and if the value is greater than n then set every element in the result array to whatever the max value in the array is. For example, given;

n = 3
A = [3, 1, 1, 2, 4, 1]
The operations would be

result [0,0,0,0,0]
operation 3 => result [0,0,1]
operation 1 => result [1,0,1]
operation 1 => result [2,0,0]
operation 2 => result [2,1,1]
operation 4 => result [2,2,2]
operation 1 => result [3,2,2]

So the return value would be [3, 2, 2]

I probably didn’t explain this perfectly so check out the link to the formal spec.

My Solution

Brute Force method

The easiest way is to just follow the instruction and do it using the brute force method. Something like:

function brute_solution(N, A) {
    let result = Array(N).fill(0);
    let maxValue = 0
    for (const operation of A) {
        if (operation === N + 1) {
            result.fill(maxValue)
        } else {
            result[operation - 1]++
            if (result[operation - 1] > maxValue) {
                maxValue = result[operation - 1]
            }
        }
    }
    return result
}

This solves the problem but fails a few performance tests.

Solution 2.0

To be honest this took me a minute to get a better solution. Calling fill() in the loop was causing the major slow down and I couldn’t see another way to keep track.

I took a coffee break then it hit me, we don’t actually need to keep track of everything. We know that the least possible value is reset with every reset all operation, therefore we can keep track of that base and use it if we are updating an index that wasn’t the max.

The other indexes won’t need updating because they will be equal to the base and we can set then all at once at the end. Using that logic I updated the function to be:

function solution(N, A) {
    let result = Array(N).fill(0);
    let maxValue = 0
    let base = 0
    for (const operation of A) {
        if (operation === N + 1) {
            base = maxValue
        } else {
            result[operation - 1] = Math.max(result[operation - 1], base)
            result[operation - 1] ++

            if (result[operation - 1] > maxValue) {
                maxValue = result[operation - 1]
            }
        }
    }
    return result.map(value => {
        return Math.max(value,base)
    })
}

This approached passed all performance tests. I think there might be a faster way but thus far it eludes me. If I run into it, I’ll update the post, but for now, that’s all I have for today.