What Part of My Code Is Making My Performance Suffer (Codility'S Maxcounter)

What part of my code is making my performance suffer? (Codility's MaxCounter)

Instead of calling Arrays.fill(answer, minimumValue); whenever you encounter a "max counter" operation, which takes O(N), you should keep track of the last max value that was assigned due to "max counter" operation, and update the entire array just one time, after all the operations are processed. This would take O(N+M).

I changed the variables names from min to max to make it less confusing.

public class Solution {

    public int[] solution(int N, int[] A) {

        int highestCounter = N;
        int maxValue = 0;
        int lastMaxValue = 0;
        int [] answer = new int[N];

        for (int i = 0; i < A.length; i++) {
            int currentCounter = A[i]; 
            int answerEquivalent = currentCounter -1;

            if(currentCounter >0 && currentCounter<=highestCounter){
                if (answer[answerEquivalent] < lastMaxValue)
                    answer[answerEquivalent] = lastMaxValue +1;
                else 
                    answer[answerEquivalent] = answer[answerEquivalent]+1; 

                if(answer[answerEquivalent] > maxValue){
                    maxValue = answer[answerEquivalent];
                }
            }

            if (currentCounter == highestCounter +1){
                lastMaxValue = maxValue;
            }
        }
        // update all the counters smaller than lastMaxValue
        for (int i = 0; i < answer.length; i++) {
            if (answer[i] < lastMaxValue)
                answer[i] = lastMaxValue;
        }
        return answer;
    }

}

Algorithm: Max Counters

This is what I came up with, but I am not sure if it works 100%:

public int[] solution(int N, int[] A) {
    int[] result = new int[N];
    int maximum = 0;
    int resetLimit = 0;

    for (int K = 0; K < A.Length; K++)
    {
        if (A[K] < 1 || A[K] > N + 1)
            throw new InvalidOperationException();

        if (A[K] >= 1 && A[K] <= N)
        {
            if (result[A[K] - 1] < resetLimit) {
                result[A[K] - 1] = resetLimit + 1;
            } else {
                result[A[K] - 1]++;
            }

            if (result[A[K] - 1] > maximum)
            {
                maximum = result[A[K] - 1];
            }
        }
        else
        {
            // inefficiency here
            //for (int i = 0; i < result.Length; i++)
            //    result[i] = maximum;
            resetLimit = maximum;
        }
    }

    for (int i = 0; i < result.Length; i++)
        result[i] = Math.Max(resetLimit, result[i]);

    return result;
}

Decreasing asymptotic time complexity

I'd like to thank you @Quinchilion and @JohnBollinger very much for your thorough analysis of the problem.

I've found an answer that passes both the correctness and performance tests. Here it is, fully commented:

struct Results solution(int N, int A[], int M) {
    struct Results result;

    int i,
        maxCounter = 0,
        lastMaxCounter = 0;

    result.C = calloc(N, sizeof(int));

    result.L = N;

    /* One way or another, We have to iterate over all the counter  
     * operations input array, which gives us an O(M) time...
     */
    for (i = 0; i < M; i++) {
        /* There is a little gotcha here. The counter operations
         * input array is 1-based, while our native C arrays are 0-based.
         * So, in order check if we have a `increment` or a `max counters`
         * operation, we have to consider the interval ]0, N].
         */
        if (A[i] > 0 && A[i] <= N) {
            /* This is an `increment` operation.
             *
             * First we need to check if there is no pending `max counter`
             * operation in this very counter.
             * This is done by checking if the value of current counter is
             * **less than** the value of `lastMaxCounter`.
             */
            if (result.C[A[i] - 1] < lastMaxCounter) {
                /* If it is, means that we have to discard the counter's
                 * current value and increment it from the value of
                 * `lastMaxCounter`.
                 */
                result.C[A[i] - 1] = lastMaxCounter + 1;
            } else {
                /* If it ain't, we just increment this counter's value.
                 */
                result.C[A[i] - 1]++;
            }

            /* We also want to keep track of the maximum counter value.
             */
            if (result.C[A[i] - 1] > maxCounter) {
                maxCounter = result.C[A[i] - 1];
            }
        } else {
            /* This is a `max counter` operation.
             * 
             * What we need to do is buffer the current `maxCounter`
             * in order to be able to update the counters later.
             */
            lastMaxCounter = maxCounter;
        }
    }

    /* At this point, if all counters have been incremented at least 
     * once after the last `max counter` operation, we are good to go.
     *
     * Since this is a rather pretentious assumption, we need to
     * double check it.
     *
     * We iterate over all counters, checking if any of them is lower
     * than the buffered `lastMaxCounter`. If it is, it means that no
     * `increment` was performed on this counter after the last
     * `max counter`, so this means that its value should be equal
     * to `lastMaxCounter`.
     *
     * This is an O(N) operation.
     *
     * So, the algorithm's time complexity is O(N) + O(M) = O(N+M)
     * and the space complexity is O(N).
     */
    for (i = 0; i < N; i++) {
        if (result.C[i] < lastMaxCounter) {
            result.C[i] = lastMaxCounter;
        }
    }

    return result;
}

Calculate the values of counters after applying all alternating operations

It is quite simple, they do lazy update. You keep track at all times of what is the value of the counter that has the highest value (currMax). Then, when you get a command to increase all counters to that maxValue, as that is too expensive, you just save that the last time you had to increase all counters to maxValue, that value was currMin.

So, when do you update a counter value to that value? You do it lazily, you just update it when you get a command to update that counter (increase it). So when you need to increase a counter, you update the counter to the max between its old value and currMin. If this was the first update on this counter since a N + 1 command, the correct value it should have is actually currMin, and that will be higher (or equal) to its old value. One you updated it, you add 1 to it. If now another increase happens, currMin doesn't actually matter, as the max will take its old value until another N + 1 command happens.

The second for is to account for counters that did not get an increase command after the last N + 1 command.

Note that there can be any number of N + 1 commands between 2 increase operations on a counter. It still follows that the value it should have is the maxValue at the time of the last N + 1 command, it doesn't really matter that we didn't update it before with the other maxValue from a previous N + 1, we only care about latest.

Codility passing car - how to approach this problem

You need to count number of cars passings. Cars are positioned on the road as input says and start driving into either one of directions. When car drives, we can easily see that it will drive by cars moving in the opposite direction, but only if they were in front of it. Essentially that can be formulated as:

1. Imagine array 0..N

2. Take element X (iterate from 0 to Nth element)

3. If value of element X is 0 then count how many 1 elements it has on the right

4. If value of element X is 1 then count how many 0 elements it has on left

5. Repeat for next X

6. Sum up and divide by 2 (cos it takes 2 cars to pass each other), that's the answer.

In case with 0 1 0 1 1 we have 3+1+2+2+2 = 10. Divide by 2 = 5 passings.

We don't count pair 2-1 because 2nd car is driving to the East and never passes the 1st car that is driving away from it to the West.

---

Related Topics