What part of my code is making my performance suffer? (Codility's MaxCounter)

Question

I have the following problem:

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.

Write a function:

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

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.

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.

---

I have answered this problem using the following code, but only got 80% as opposed to 100% performance, despite having O(N+M) time complexity:

public class Solution {

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

        int highestCounter = N;
        int minimumValue = 0;
        int lastMinimumValue = 0;
        int [] answer = new int[N];

        for (int i = 0; i < A.length; i++) {
            int currentCounter = A[i]; 
            int answerEquivalent = currentCounter -1;

            if(currentCounter >0 && currentCounter<=highestCounter){
                answer[answerEquivalent] = answer[answerEquivalent]+1; 

                if(answer[answerEquivalent] > minimumValue){
                    minimumValue = answer[answerEquivalent];
                }
            }

            if (currentCounter == highestCounter +1 && lastMinimumValue!=minimumValue){
                lastMinimumValue = minimumValue;
                Arrays.fill(answer, minimumValue);
            }
        }
        return answer;
    }

}

Where is my performance here suffering? The code gives the right answer, but does not perform up-to-spec despite having the right time complexity.

Answer 1

Instead of calling Arrays.fill(answer, minimumValue); whenever you encounter a "max counter" operation, which takes O(N), you should keep track of the last max value that was assigned due to "max counter" operation, and update the entire array just one time, after all the operations are processed. This would take O(N+M).

I changed the variables names from min to max to make it less confusing.

public class Solution {

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

        int highestCounter = N;
        int maxValue = 0;
        int lastMaxValue = 0;
        int [] answer = new int[N];

        for (int i = 0; i < A.length; i++) {
            int currentCounter = A[i]; 
            int answerEquivalent = currentCounter -1;

            if(currentCounter >0 && currentCounter<=highestCounter){
                if (answer[answerEquivalent] < lastMaxValue)
                    answer[answerEquivalent] = lastMaxValue +1;
                else 
                    answer[answerEquivalent] = answer[answerEquivalent]+1; 

                if(answer[answerEquivalent] > maxValue){
                    maxValue = answer[answerEquivalent];
                }
            }

            if (currentCounter == highestCounter +1){
                lastMaxValue = maxValue;
            }
        }
        // update all the counters smaller than lastMaxValue
        for (int i = 0; i < answer.length; i++) {
            if (answer[i] < lastMaxValue)
                answer[i] = lastMaxValue;
        }
        return answer;
    }

}

Answer 2

The following operation is O(n) time:

Arrays.fill(answer, minimumValue);

Now, if you are given a test case where the max counter operation is repeated often (say n/3 of the total operations) - you got yourself an O(n*m) algorithm (worst case analysis), and NOT O(n+m).

You can optimize it to be done in O(n+m) time, by using an algorithm that initializes an array in O(1) every time this operation happens.
This will reduce worst case time complexity from O(n*m) to O(n+m)¹

---

_{(1)Theoretically, using the same idea, it can even be done in O(m) - regardless of the size of the number of counters, but the first allocation of the arrays takes O(n) time in java}

Answer 3

This is a bit like @Eran's solution but encapsulates the functionality in an object. Essentially - keep track of a max value and an atLeast value and let the object's functionality do the rest.

private static class MaxCounter {

    // Current set of values.
    final int[] a;
    // Keeps track of the current max value.
    int currentMax = 0;
    // Min value. If a[i] < atLeast the a[i] should appear as atLeast.
    int atLeast = 0;

    public MaxCounter(int n) {
        this.a = new int[n];
    }

    // Perform the defined op.
    public void op(int k) {
        // Values are one-based.
        k -= 1;
        if (k < a.length) {
            // Increment.
            inc(k);
        } else {
            // Set max
            max(k);
        }
    }

    // Increment.
    private void inc(int k) {
        // Get new value.
        int v = get(k) + 1;
        // Keep track of current  max.
        if (v > currentMax) {
            currentMax = v;
        }
        // Set new value.
        a[k] = v;
    }

    private int get(int k) {
        // Returns eithe a[k] or atLeast.
        int v = a[k];
        return v < atLeast ? atLeast : v;
    }

    private void max(int k) {
        // Record new max.
        atLeast = currentMax;
    }

    public int[] solution() {
        // Give them the solution.
        int[] solution = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            solution[i] = get(i);
        }
        return solution;
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder("[");
        for (int i = 0; i < a.length; i++) {
            s.append(get(i));
            if (i < a.length - 1) {
                s.append(",");
            }
        }
        return s.append("]").toString();
    }
}

public void test() {
    System.out.println("Hello");
    int[] p = new int[]{3, 4, 4, 6, 1, 4, 4};
    MaxCounter mc = new MaxCounter(5);
    for (int i = 0; i < p.length; i++) {
        mc.op(p[i]);
        System.out.println(mc);
    }
    int[] mine = mc.solution();
    System.out.println("Solution = " + Arrays.toString(mine));
}

Answer 4

My solution: 100\100

class Solution
    {
        public int maxCounterValue;

    public int[] Counters;

    public void Increase(int position)
    {
        position = position - 1;
        Counters[position]++;
        if (Counters[position] > maxCounterValue)
            maxCounterValue = Counters[position];
    }

    public void SetMaxCounter()
    {
        for (int i = 0; i < Counters.Length; i++)
        {
            Counters[i] = maxCounterValue;
        }
    }



    public int[] solution(int N, int[] A)
    {
        if (N < 1 || N > 100000) return null;
        if (A.Length < 1) return null;

        int nlusOne = N + 1;
        Counters = new int[N];
        int x;
        for (int i = 0; i < A.Length; i++)
        {
            x = A[i];
            if (x > 0 && x <= N)
            {
                Increase(x);
            }

            if (x == nlusOne && maxCounterValue > 0) // this used for all maxCounter values in array. Reduces addition loops
                SetMaxCounter();
            if (x > nlusOne)
                return null;
        }

        return Counters;

    }
}

Answer 5

1. ( @molbdnilo : +1 !) As this is just an algorithm test, there's no sense getting too wordy about variables. "answerEquivalent" for a zero-based array index adjustment? Gimme a break ! Just answer[A[i] - 1] will do.
2. Test says to assume A values always lie between 1 and N+1. So checking for this is not needed.
3. fillArray(.) is an O(N) process which is within an O(M) process. This makes the whole code into an O(M*N) process when the max complexity desired is O(M+N). The only way to achieve this is to only carry forward the current max value of the counters. This allows you to always save the correct max counter value when A[i] is N+1. The latter value is a sort of baseline value for all increments afterwards. After all A values are actioned, those counters which were never incremented via array entries can then be brought up to the all-counters baseline via a second for loop of complexity O(N).

Look at Eran's solution.

Answer 6

This is how we can eliminate O(N*M) complexity.
In this solutions, instead of populating result array for every A[K]=N+1, I tried to keep what is min value of all elements, and update result array once all operation has been completed.

If there is increase operation then updating that position :

  if (counter[x - 1] < minVal) {
     counter[x - 1] = minVal + 1;
  } else {
     counter[x - 1]++;
  }

And keep track of minVal for each element of result array.

Here is complete solution:

public int[] solution(int N, int[] A) {
    int minVal = -1;
    int maxCount = -1;

    int[] counter = new int[N];

    for (int i = 0; i < A.length; i++) {
        int x = A[i];

        if (x > 0 && x <= N) {
            if (counter[x - 1] < minVal) {
                counter[x - 1] = minVal + 1;

            } else {
                counter[x - 1]++;
            }

            if (maxCount < counter[x - 1]) {
                maxCount = counter[x - 1];
            }
        }

        if (x == N + 1 && maxCount > 0) {
            minVal = maxCount;
        }
    }

    for (int i = 0; i < counter.length; i++) {
        if (counter[i] < minVal) {
            counter[i] = minVal;
        }
    }

    return counter;
}

Answer 7

This is my swift 3 solution (100/100)

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
  var counters = Array(repeating: 0, count: N)
  var _max = 0
  var _min = 0
  for i in A {
    if counters.count >= i {
      let temp = max(counters[i-1] + 1, _min + 1)
      _max = max(temp, _max)
      counters[i-1] = temp
    } else {
      _min = _max
    }
  }
  return counters.map { max($0, _min) }
}