# Time complexity of Max counters

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 ≤ XN, 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).

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))1
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-pattern2.

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

• You can improve the running time to O(n) by keeping track of two maximums: the current maximum of all array cells, and the most recent maximum to which all cells were updated. Then, before increasing the value in a cell, make sure its value is at least the update-maximum that you're keeping track of, otherwise set it to that update-maximum. (Reading the array is left implicit here, but this check-and-update should also be done each time you want to read a cell.) Sep 14, 2018 at 13:59
• @MeesdeVries Thank you for the suggestion, I've updated my answer with an implementation of it. Sep 14, 2018 at 16:26
• You can shorten normalizeCounters with counters[index] = java.lang.Math.max(counters[index],base). Additionally, I don't think you need the out of bounds check in getCounterValue. If it's asking for an out of bounds counter, it SHOULD throw the appropriate exception. Sep 14, 2018 at 19:00