Time complexity of Max counters

Question

As per the instructions are given in MaxCounters-Codility,

You are given N counters, initially set to 0, and you have two possible operations on them:

• increase(X) − counter X is increased by 1,

• max counter − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X), if A[K] = N + 1 then operation K is max counter.

I have written this code

public int[] maxCount(int[]A,int N) {
    int[] I = new int[N];
    for (int i = 0; i < A.length; i++) {
        try {
            I[A[i] - 1]++;
        } catch (Exception e) {
            Arrays.sort(I);
            Arrays.fill(I, I[I.length - 1]);
        }
    }
    return I;
}

It gives correct answers for all test cases. Any Idea to do this with time complexity O(N). Its currently on O(N*M).

Answer 1

Lets start with the time complexity of your current algorithm:

for (int i = 0; i < A.length; i++) has a time complexity of O(M) (Length of array 'A' is 'M')
Arrays.sort(I) has a time complexity of O(N*log(N))¹
Arrays.fill(I, I[I.length - 1]) has a time complexity of O(N) (The number of counters)

That means the complexity of your current algorithm is O(N^2 * log(N) * M).

You can replace the sorting by keeping track of the maximum value for all counters like this:

public int[] maxCount(int[] A, int N)
{
    int[] I = new int[N];
    //Initialize the max value to 0
    int max = 0;

    for (int i = 0; i < A.length; i++)
    {
        if (A[i] == N + 1)
        {
            Arrays.fill(I, max);
        }
        else
        {
            I[A[i] - 1]++;

            if (I[A[i] - 1] > max)
            {
                //Update the max value 
                max = I[A[i] - 1];
            }
        }
    }
    return I;
}

The time complexity of this version is now O(M * N). This version is also using if statements to control the flow of the program as opposed to exceptions which is an anti-pattern².

UPDATE: I've used the suggestion of Mees de Vries from his comment to implement a data structure for the problem. The complexity of the function reading the instruction incrementCounters() is O(n).

public class SynchronizedCounters
{
    private int[] counters;
    private int size;
    private int base = 0;
    private int max = 0;
    private final int INSTRUCTION_OFFSET = 1;

    public SynchronizedCounters(int size)
    {
        this.size = size;
        this.counters = new int[size];
    }

    public void incrementCounters(int[] instructions)
    {
        for (int instruction : instructions)
        {
            int instruct = instruction - INSTRUCTION_OFFSET;

            if (instruct >= size)
            {
                base = max;
            }
            else
            {
                normalizeCounter(instruct);

                counters[instruct]++;

                if (counters[instruct] > max)
                {
                    max = counters[instruct];
                }
            }
        }
    }

    public Integer getCounterValue(int counter)
    {
        normalizeCounter(counter);
        return counters[counter];
    }

    private void normalizeCounter(int index)
    {
        counters[index] = java.lang.Math.max(counters[index],base);
    }
}

Example using the class:

public static void main(String[] args)
    {
        SynchronizedCounters synchronizedCounters = new SynchronizedCounters(5);
        synchronizedCounters.incrementCounters(new int[]{1, 1, 1, 3, 2, 1, 1, 6, 2, 3});
        System.out.println("Value of first counter: " + synchronizedCounters.getCounterValue(0));
    }

Output:

Value of first counter: 5

¹ https://stackoverflow.com/questions/21219777/the-running-time-for-arrays-sort-method-in-java

² https://web.archive.org/web/20140430044213/http://c2.com/cgi-bin/wiki?DontUseExceptionsForFlowControl