Java solution to Codility MaxCounters problem (Lesson 4 – Counting Elements) which scored 100%. The problem is to calculate the final values of counters in an array, after applying a sequence of two different operations: 1) increment a specific counter by 1 and 2) set all counters to the maximum of any counter.
A brute force approach would take too long, so the strategy is to pass through the array twice. In the first pass, set all counters for explicitly specified elements. In the second pass, set counters for elements that were never explicitly specified but have been globally reset. This avoids having to repeatedly reset counters for elements that were never explicitly specified.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class MaxCounters {
public int[] solution(int N, int[] A) {
int [] counters = new int[N];
int maxCounter = 0; //for the next re-set will know what high score to set all values
int lastResetCounter = 0; //for setting values that were never explicitly set - at the end
for(int i=0; i<A.length; i++) {
if(A[i] <= N) {
if(counters[A[i]-1] < lastResetCounter) { counters[A[i]-1] = lastResetCounter; //bring it up to last reset value } counters[A[i]-1]++; //store max counter in case need to set all counters to this value on next reset if(counters[A[i]-1] > maxCounter) {
maxCounter = counters[A[i]-1];
}
}
else {
//keep track of last reset counter
lastResetCounter = maxCounter;
}
}
//set all values to last reset value that was never explicitly changed after last reset
for(int i=0; i<counters.length; i++) {
if(counters[i] < lastResetCounter) {
counters[i] = lastResetCounter;
}
}
return counters;
}
}
TestNG test cases for this problem which all passed:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
import com.codility.lesson04.countingelements.MaxCounters;
public class MaxCountersTests {
private MaxCounters solution;
@BeforeTest
public void setUp() {
solution = new MaxCounters();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { 5, new int [] { 3, 4, 4, 6, 1, 4, 4 }, new int [] { 3, 2, 2, 4, 2 } },
new Object [] { 3, new int [] { 2, 1, 2 }, new int [] { 1, 2, 0 } },
new Object [] { 3, new int [] { 2, 1, 2, 2, 1, 2 }, new int [] { 2, 4, 0 } },
new Object [] { 2, new int [] { 2, 1, 3, 2 }, new int [] { 1, 2 } },
new Object [] { 2, new int [] { 2, 1, 3, 2, 3, 1, 2 }, new int [] { 3, 3 } },
new Object [] { 1, new int [] { 2, 1, 2 }, new int [] { 1 } },
};
}
@Test(dataProvider = "test1")
public void verifySolution(int pInt, int [] pA, int [] pExpected) {
int [] actual = solution.solution(pInt, pA);
Assert.assertEquals(actual.length, pExpected.length);
for(int i=0; i<actual.length; i++) {
Assert.assertEquals(actual[i], pExpected[i]);
}
}
}