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

• Mees de Vries: 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.)
• DobromirM: @MeesdeVries Thank you for the suggestion, I've updated my answer with an implementation of it.
• Ethan: 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.