java codility Max-Counters

Question

I have been trying to solve the below task:

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 zero-indexed array A of M integers is given. This array represents consecutive operations:

    if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
    if A[K] = N + 1 then operation K is max_counter.

For example, given integer N = 5 and array A such that:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

struct Results {
  int * C;
  int L;
}; 

Write a function:

struct Results solution(int N, int A[], int M); 

that, given an integer N and a non-empty zero-indexed array A consisting of M integers, returns a sequence of integers representing the values of the counters.

The sequence should be returned as:

    a structure Results (in C), or
    a vector of integers (in C++), or
    a record Results (in Pascal), or
    an array of integers (in any other programming language).

For example, given:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Assume that:

    N and M are integers within the range [1..100,000];
    each element of array A is an integer within the range [1..N + 1].

Complexity:

    expected worst-case time complexity is O(N+M);
    expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Here is my solution:

import java.util.Arrays;

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

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

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

                if (localValue > currentMax) {
                    currentMax = localValue;
                }
            }

        }

        return countersArray;
    }
}

Here is the code valuation: https://codility.com/demo/results/demo6AKE5C-EJQ/

Can you give me a hint what is wrong with this solution?

Answer 1

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;
    }
}

Answer 2

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.

Answer 3

Another solution that I have developed and might be worth considering: http://codility.com/demo/results/demoM658NU-DYR/

Answer 4

This is the 100% solution of this question.

// you can also use imports, for example:
// import java.math.*;
class Solution {
    public int[] solution(int N, int[] A) {
        int counter[] = new int[N];
        int n = A.length;
        int max=-1,current_min=0;

        for(int i=0;i<n;i++){
            if(A[i]>=1 && A[i]<= N){
                if(counter[A[i] - 1] < current_min) counter[A[i] - 1] = current_min;
                counter[A[i] - 1] = counter[A[i] - 1] + 1;
                if(counter[A[i] - 1] > max) max = counter[A[i] - 1];
            }
            else if(A[i] == N+1){
                current_min = max;
            }
        }
        for(int i=0;i<N;i++){
            if(counter[i] < current_min) counter[i] =  current_min;
        }
        return counter;
    }
}