Ok, this is first interesting one. The concept goes like this.

We iterate through input array and increase a value for element in counterArray. Elements in counterArray represents number of repetitions in inputArray of the value of index in counterArray. We intuitively iterate through inputArray until we get to element with value of N+1. Then reset all the fields in counterArray to zero and continue iterating. Every time we get to N+1 element we remember the value of biggest element in counterArray. After that loop we iterate through counterArray and increase every element by the biggest remembered element.

Now, this concept works fine but when we want to reset an array we hit the performance lag. At first I created zeroedArray and

1 |
counterArray = zeroedArray; |

Even tho, JAVA is supposed to be “pass by value” language, this way it passes a reference to the zeroedArray so changes to counterArray reflect to zeroedArray so it isn’t zeroed any more. 🙂

Second thing I tried was

1 |
counterArray = new int[N]; |

This way everything worked fine but the code was too slow. I tried to optimise it but it was always around 11 seconds on big queries while the limit was 8.

So the best solution to copying an array to another array by value is to use

1 |
System.arraycopy(sourceArray, 0, destinationArray, 0, sourceArray.length); |

So here is the entire solution with 100/100 score.

1 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 |
// Result: 100/100 public static int[] solution_4_MaxCounters(int N, int[] A) { int[] counterArray = new int[N]; final int[] zeroedArray = new int[N]; int biggestCounter = 0; int maxCounter = 0; for (int i = 0; i < A.length; i++) { if (A[i] <= N) { counterArray[A[i] - 1]++; if (counterArray[A[i] - 1] + maxCounter > biggestCounter) biggestCounter = counterArray[A[i] - 1] + maxCounter; } else if (A[i] == N + 1) { maxCounter = biggestCounter; System.arraycopy(zeroedArray, 0, counterArray, 0, zeroedArray.length); } } for (int j = 0; j < counterArray.length; j++) counterArray[j] += maxCounter; return counterArray; } |