Java Solution to Codility’s Max Counters Problem

June 28, 2018

Hey Developer,

I am bringing you another high quality Java solution. This time, I am solving the Max Counters problem which can be found here.

My solution has runtime of O(N + M) and space complexity of O(N) as the counter array needs to be stored. This problem is very straight forward, you are just following the steps in the description. If you were to implement the naive solution, then all you would need are 2 for loops. However, this leads to a runtime of O(N * M). So what can we do?

In software development, there is a concept of performing lazy writes, which just means that we can wait to update our data until we need it as opposed to updating it right away. One of the benefits of this technique is performance, which is what we need to solve this problem. In the solution to this problem, every time max counters operation is called, we wait until a later time to update our data.

Explanation:

1. Create a variable to store the maximum value present in counters. – maxCount
2. Create a variable to store the minimum value that every counter in counters should have. – minCount
3. Iterate through A
• If max counter, then we update the value of minCount
• if increase(X)
1. Update value of counter to the minimum value it should have, if needed
2. Add 1 to the value of the counter
3. Update maxCount, if needed
4. Iterate through counters and make sure every value is at least equal to minCount

Below is the code for my Java solution.

class Solution {
 
	public int[] solution(int N, int[] A) {
 
        // variable to store the number of elements in A
	int A_N = A.length;
	// array to store counters
        int [] counters = new int[N];
        // variable to store the current maximum count
        int maxCount = 0;
        // variable to store the current minimum count
        int minCount = 0;
 
 
        for (int i = 0; i < A_N; i++) {
        	// if max counter
        	if (A[i] == N + 1) {
        		// minCount is now the minimum number every counter should have
        		minCount = maxCount;
        	}
        	// increase(X)
        	else {
        		// if the variable is less than what it should be, we update it
        		if (counters[A[i]-1] < minCount) {
        			counters[A[i]-1] = minCount;
        		}
        		// after the variable is updated, then we increment it
        		counters[A[i]-1] += 1;
        		// finally, we update max count if needed
        		if (maxCount < counters[A[i]-1]) {
        			maxCount = counters[A[i]-1];
        		}
        	}
 
        }
 
        // make sure that every variable in counter has at least the minimum value in it
        for (int i = 0; i < N; i++){
            if (counters[i] < minCount) {
        		counters[i] = minCount;
        	}
        }
 
        return counters;
    }
}