java codility Max-Counters

The problem is that when you get lots of max_counter operations you get lots of calls to Arrays.fill which makes your solution slow.

You should keep a currentMax and a currentMin:

• When you get a max_counter you just set currentMin = currentMax.
• If you get another value, let's call it i:
  • If the value at position i - 1 is smaller or equal to currentMin you set it to currentMin + 1.
  • Otherwise you increment it.

At the end just go through the counters array again and set everything less than currentMin to currentMin.

The problem comes with this piece of code:

for (int iii = 0; iii < A.length; iii++) {
     ...
     if (currentValue == condition) {
         Arrays.fill(countersArray, currentMax);
     }
     ...
}

Imagine that every element of the array A was initialized with the value N+1. Since the function call Arrays.fill(countersArray, currentMax) has a time complexity of O(N) then overall your algorithm will have a time complexity O(M * N). A way to fix this, I think, instead of explicitly updating the whole array A when the max_counter operation is called you may keep the value of last update as a variable. When first operation (incrementation) is called you just see if the value you try to increment is larger than the last_update. If it is you just update the value with 1 otherwise you initialize it to last_update + 1. When the second operation is called you just update last_update to current_max. And finally, when you are finished and try to return the final values you again compare each value to last_update. If it is greater you just keep the value otherwise you return last_update

class Solution {
    public int[] solution(int N, int[] A) {

        final int condition = N + 1;
        int currentMax = 0;
        int lastUpdate = 0;
        int countersArray[] = new int[N];

        for (int iii = 0; iii < A.length; iii++) {
            int currentValue = A[iii];
            if (currentValue == condition) {
                lastUpdate = currentMax
            } else {
                int position = currentValue - 1;
                if (countersArray[position] < lastUpdate)
                    countersArray[position] = lastUpdate + 1;
                else
                    countersArray[position]++;

                if (countersArray[position] > currentMax) {
                    currentMax = countersArray[position];
                }
            }

        }

        for (int iii = 0; iii < N; iii++) {
           if (countersArray[iii] < lastUpdate)
               countersArray[iii] = lastUpdate;
        }

        return countersArray;
    }
}