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

up vote 6 down vote accepted

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))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

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

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

  • 2
    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.) – Mees de Vries Sep 14 at 13:59
  • 1
    @MeesdeVries Thank you for the suggestion, I've updated my answer with an implementation of it. – DobromirM Sep 14 at 16:26
  • 1
    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. – Ethan Sep 14 at 19:00

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.